C++ : 반복되는 변형에 대한 재귀 함수, 다른 문자의 양으로 정렬

Question

다음과 같은 변형을 생성하는 함수가 있습니다. 111, 112, ..., 133, 211, 212, ..., 233, 311, ..., 333. 생성 된 시퀀스의 길이는 항상 사전의 길이와 일치합니다. 4 개의 기호를 사용하면 1111에서 4444가됩니다.

그래프 채색을위한 무차별 대입 알고리즘에서 수행됩니다. Google은 가능한 한 다른 색상을 사용하지 않는 올바른 순서를 찾으려고합니다. 즉, 12343과 12321이 모두 해결책 인 경우 후자를 선호합니다.

지금 당장 나는 모든 시퀀스가 ​​올바른지 확인한 다음 최상의 결과를 저장합니다. 정말 좋은 코드는 아닙니다.

그래서 교수님은 특정 순서로 변형을 생성하는 함수를 작성하라고했습니다. 이 순서는 다음과 같이 서로 다른 숫자로 정렬해야합니다 : 111, 222, 333; 112, 113, 121, ..., 323; 123, 213.이 경우, 121이 맞다는 것을 알게되면, 우리는 이미 그것이 최선의 해결책이라는 것을 알고 있기 때문에 멈추게됩니다.

아이디어는 가능한 한 많은 시퀀스 검사를 건너 뛰고 코드가 더 빨리 실행되도록하는 것입니다. 제발 도와주세요 :)

를 지금 나는이 코드를 사용합니다

init 함수를

std::vector<int> res; //contains the "alphabet" 
res.reserve(V); 
for (int i = V - 1; i >= 0; i--) { 
    res.push_back(i); 
} 

std::vector<int> index(res.size()); 
std::vector<int> bestresult(V); //here goes the best answer if it's found 
for (int i = V - 1; i >= 0; i--) { 
    bestresult.push_back(i); 
} 
int bestcolors = V; 
permutate(res, index, 0, bestresult, bestcolors); 

result = bestresult; 

순열 :

void Graph::permutate(const std::vector<int>& s, std::vector<int>& index, std::size_t depth, std::vector<int>& bestres, int &lowestAmountOfColors) 
{ 
if (depth == s.size()) { 
    //doing all needed checks and saving bestresult here; 

    return; 
} 

for (std::size_t i = 0; i < s.size(); ++i) { 
    index[depth] = i; 
    permutate(s, index, depth + 1, bestres, lowestAmountOfColors); 
} 
} 

가 어떻게 이러한 기능을 변경할 수 있습니까?

Answer 1

도전 과제는 색상의 모든 순열을 찾아 올바른 그래프 색상으로 표시되는지 테스트하는 것입니다. 불행히도, 그것은 기하 급수적입니다. 따라서 가장 작은 솔루션을 먼저 확인하는 방식으로 순열을 검색해야하며 솔루션 공간을 극적으로 정리해야합니다.

먼저 가장 작은 솔루션을 찾으려면 사용 가능한 색상 수를 제한하고 색상 수를 늘리기 전에 해당 순열을 소진해야합니다. 아주 간단합니다. 우리는 N 정점에 대해 n 색을 고려하는 함수가 필요합니다. 꼭지점 수는 고정되어 있지만 n = 1, n = 2 등으로 간주합니다.

함수 내에서 우리는 1, 2, ... n의 다양한 조합을 얻기 위해 충분한 반복을 필요로한다는 것을 알고 있습니다. 총 N 개의 다른 값. 그래서 나는 수의 벡터를 만들었습니다. 이 벡터는 n 개의 엔트리를 가지며 값은 N까지 합계됩니다.

예를 들어, 7 개의 꼭지점이있는 그래프에 대해 세 가지 색상 솔루션을 고려할 때 하나의 가능한 카운트 배열은 {4, 3, 1}이됩니다. 후보 {1, 1, 1, 1, 2, 2, 2, 3}을 생성하는 데 사용됩니다. 색상 1이 4 번 나타납니다. 색상 2가 3 번 나타납니다. 색상 3이 한 번 나타납니다.

이 카운트 배열에 대한 멋진 점은 색상이 서로 바뀔 수 있기 때문에 가장 큰 것으로 정렬되는 한 그 조합은 우리가 고려한 다른 조합을 복제 할 수 없다는 것입니다. (오케이, 완전히 정확하지는 않지만, 색상이 같은 수의 중복이있을 수 있지만, 우리는 전체 관점에서 보았을 때 많은 순열을 제거했습니다).

카운트 배열을 실제 후보 솔루션으로 줄이면 순열이 아닌 조합을 사용하여 모든 순서를 찾을 수 있습니다. 그러면 후보자 수가 줄어 듭니다. Google next_combination을 사용하여이를 수행하는 방법을 보여주는 좋은 코드를 찾습니다.

카운트 배열을 생성 할 때 모든 값을 1로 초기화 한 다음 나머지 카운트를 모두 첫 번째 색에 추가했습니다. 내가 counts 배열을 충족 모든 조합을 검색합니다. 그런 다음 카운트를 정렬 된 방식으로 오른쪽으로 이동하여 다음 후보를 얻습니다.

---

따라서 요약하면 find_minimum_graph_coloring에는 solve_for_n을 호출하는 for 루프가 있습니다. 이 함수는 n의 해당 값에 대한 가능한 모든 카운트 배열을 생성하고 다른 함수를 호출합니다. 이 함수는 해당 개수 배열에 대한 모든 조합을 검사합니다.

첫 번째 for 루프는 작은 수의 색상을 먼저 확인하므로 솔루션을 찾으면 즉시 반환 할 수 있습니다. 카운트 - 배열 표기법은 많은 동등한 채색을 제거하므로 {1, 1, 2}를 고려하면 {2, 2, 1}을 시도하지 않습니다.