C++：繰り返しのバリエーションの再帰関数。異なる文字の数で並べ替え

Question

111,112、...、133,211,212、...、233,311,312などのバリエーションを生成する関数があります。 ...、333.生成されたシーケンスの長さは常に辞書の長さに一致します。 4シンボルの場合、1111から4444になります。

これは、グラフの色付けのためにブルートフォースアルゴリズムで行われます。できるだけ色の違う正しいシーケンスを見つけることを試みています。つまり、12343と12321の両方が解決策である場合は、後者を好むでしょう。

今のところ、すべてのシーケンスが正しいかどうかを確認して、最良の結果をプロセスに保存します。それは本当に良いコードではありません。

教授は、特定の順序でバリエーションを生成する関数を作成するように私に依頼しました。これらのシーケンスは、次のような異なる数の量によって順序付けされるべきです：111,222,333; 112、113、121、...、323;この場合、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; 

permutate：

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つの頂点を持つグラフに対して3つのカラー解を考えると、可能な1つのカウント配列は{4,3,1}になります候補{1,1,1,2,2,2,3}を生成するために使用される。色1が4回現れる。色2が3回現れる。カラー3が1回表示されます。

このカウント配列についてのクールなことは、色が交換可能であるため、最小値から最大値にソートされている限り、その組み合わせでは他の組み合わせを複製できないことです。 （確かに、完全に正確ではない、色が同じ数を持つときにはいくつかの重複があるが、今まで見てきた多くの順列を取り除いた。

counts配列を実際の候補解に減らすと、順列ではなく組み合わせを使用してすべての順序を見つけることができます。これにより候補者が少なくなります。 Googleのnext_combinationを使用して、これを行う方法を示す良いコードを見つけます。

カウント配列を生成すると、すべての値が1に初期化され、残りのカウントがすべて最初の色に追加されました。カウント配列を満たすすべての組み合わせを検索します。次に、ソートされたままカウントを右にシフトして次の候補を取得します。

---

したがって、find_minimum_graph_coloringにはsolve_for_nを呼び出すforループがあります。この関数は、nの値に対して可能なすべてのカウント配列を生成し、別の関数を呼び出します。この関数は、そのcounts配列のすべての組み合わせをチェックします。

最初のforループは最初に色の数を確認するので、解決策を見つけたら直ちに戻ることができます。カウント配列表記法では、多くの同等の色が削除されるので、{1、1、2}を考えれば、{2、2、1}を試しません。