T = {0, 1}2つの要素のセットを入力として受け取り、次のすべての組み合わせをk生成するアルゴリズムを探しています。kT
000
001
010
011
100
101
110
111
上記の例のkように、が小さい場合は繰り返し実装するのは簡単です。k=3アルゴリズムがに依存しないように再帰的アルゴリズムを設計する方法のアイデアk。
質問する
3921 次
6 に答える
6
再帰的に行うことができます。これが一種の学習演習であると仮定すると、Cプログラムの代わりに擬似コードを提供します。
generate (int pos, int element[T], int current[N])
if pos == N
print (current)
return
for i : 0..T
current[pos] = element[i]
generate(pos+1, element, current)
end
上の3行はベースケースです。posゼロから始まりcurrent、再帰呼び出しの現在のレベルで埋める必要がある配列内の位置を示します。にpos達するNと、現在の組み合わせを印刷して前のレベルに戻ります。
下の3行はループであり、の場合の問題の解決策のネストされたループに似ていますk=3。「ネスティング」は再帰を通じて動的に発生します。再帰呼び出しの次のレベルは、「ループネスティング」の別のレベルと考えることができます。基本的に、再帰的ソリューションを使用すると、実行時にのみ認識されるNネストされたループを構築できます。N
于 2012-09-18T10:38:04.003 に答える
2
再帰的なアルゴリズムは必要ありません。リストを見ると、「パターン」が表示されているはずです。
これは、0から2^k-1までの2進数です。したがって、簡単な解決策は数えることです。
for (i = 0; i < (1<<k); i++) {
// generate the binary representation of i
for (c = k-1 ; c >= 0; c--) {
r = i >> c;
printf((r & 1) ? "1" : "0");
}
printf("\n");
}
編集：再帰的なアプローチが必要な場合は、長さ全体を再帰することで簡単に行うことができます。疑似コードを指定します（私の目には、再帰は割り当て/宿題の場合にのみ意味があり、自分で何かを行う必要があります） ：
print_all_combos(int k, char* prefix) {
if (k == 0) {
printf("%s\n", prefix);
return;
}
append(prefix, "0");
print_all_combos(k - 1 , prefix);
remove_last_char(prefix);
append(prefix, "1");
remove_last_char(k - 1, prefix);
}
kと空の文字列をパラメータとして呼び出します。
于 2012-09-18T10:43:21.113 に答える
2
設計時にkがわかっている場合は、kループを使用してすべてのkの組み合わせを生成するのは簡単です。つまり、すべての4の組み合わせが必要な場合は、4つのループを使用して生成できます。
for c1=0 to 1
for c2=0 to 1
for c3=0 to 1
for c4=0 to 1
print c1,c2,c3,c4
設計時にkがわからない場合は、kループをエミュレートする方法が必要になります。これは簡単です。サイズkの配列を作成し、インデックスiに現在のciの値（ループ番号iのインデックス）を格納します。
c : array[1..k]
fill(c,0) // initialize all the cells with 0
do
for i=1 to k
print c[i]
while increment(c) // get next values
increment次の値を取得し、すべての値が使用されている場合はfalseを返し、それ以外の場合はtrueを返します。
increment(c : array[1..k])
begin
i=k
do
c[i]=c[i]+1;
if c[i]=2 // i.e. MAX+1
c[i]=0
i=i-1 // incerment previous position
else
return true // increment done
end if
while (i>1)
// here we need to increment the first position
c[i]=c[i]+1
if c[i]=2 // we looped thru all the values
c[i]=0
return false
end if
return true
end
このメソッドは、任意のベースの任意のループ（=ループごとに異なる最大値）または異なる開始値、ステップなどで一般化できます...このメソッドは、繰り返しなどの辞書式の組み合わせを生成するために一般化することもできます... google for走行距離計またはTAOCPKnuthVolume3の筋肉束2および3をご覧ください。
于 2012-09-18T10:59:26.203 に答える
0
あなたが提供する例に基づいて、あなたは組み合わせではなく、k-順列を参照していると思います。ウィキペディアから引用：
組み合わせは、（順列とは異なり）順序が重要ではない、より大きなグループからいくつかのものを選択する方法です。
于 2013-07-02T19:07:44.217 に答える
0
#include<stdio.h>
#include<conio.h>
void calAns(int idx, int f[3]);
int main()
{
int f[3];
calAns(0,f);
getch();
return 0;
}
void calAns(int idx, int f[3])
{
if(idx == 3)
{
int i;
for(i = 0; i<3; i++)
printf("%d",f[i]);
printf("\n");
return;
}
f[idx] = 0;
calAns(idx+1, f);
f[idx] = 1;
calAns(idx+1, f);
}
于 2016-09-20T15:52:38.170 に答える
0
@Sergey Kalinichenkoのおかげで、少し再帰的なアプリを作成しました。これはJavaコードですが、誰かに役立つことを願っています。
キーメソッドはgenerateCombinationsRecursivelyです。
テストクラス：
public class CombinationOKTest {
CombinationOK combinationOK;
@BeforeEach
void setUp() {
combinationOK = new CombinationOK();
}
@Test
void allCombinationsWithTwoElementsAndLengthThreeBinary() {
List<Integer> elementList = List.of(0, 1);
int combinationLength = 3;
List<List<Integer>> combinationList =
combinationOK.getAllCombinations(elementList, combinationLength);
assertEquals(8, combinationList.size());
assertEquals(List.of(
List.of(0, 0, 0),
List.of(0, 0, 1),
List.of(0, 1, 0),
List.of(0, 1, 1),
List.of(1, 0, 0),
List.of(1, 0, 1),
List.of(1, 1, 0),
List.of(1, 1, 1)),
combinationList);
}
}
実装クラス：
public class CombinationOK {
public List<List<Integer>> getAllCombinations(List<Integer> elementList,
int combinationLength) {
List<List<Integer>> combinationList = new ArrayList<>();
Integer[] combination = new Integer[combinationLength];
generateCombinationsRecursively(elementList, combinationList, combination, 0);
System.out.println();
System.out.println(combinationList);
return combinationList;
}
public class CombinationOK {
public List<List<Integer>> getAllCombinations(List<Integer> elementList,
int combinationLength) {
List<List<Integer>> combinationList = new ArrayList<>();
Integer[] combination = new Integer[combinationLength];
generateCombinationsRecursively(elementList, combinationList, combination, 0);
System.out.println();
System.out.println(combinationList);
return combinationList;
}
/**
*
* Magic is done in this recursive method <code>generateCombinationsRecursively</code>.
*
* @param elementList elements that combinations are made of (T)
* @param combinationList is resulting list of combinations as a result of recursive method
* @param combination is array of elements, single combination with variable length (k)
* @param position of one element from the list <code>elementList</code> in the <code>combination</code> array
*
*/
private void generateCombinationsRecursively(List<Integer> elementList,
List<List<Integer>> combinationList,
Integer[] combination,
int position) {
if (position == combination.length) {
System.out.println(Arrays.asList(combination));
combinationList.add(new ArrayList<>(Arrays.asList(combination)));
return;
}
for (int i = 0; i < elementList.size(); i++) {
combination[position] = elementList.get(i);
generateCombinationsRecursively(
elementList, combinationList, combination, position + 1);
}
}
}
概要：
主な機能は、この再帰的な方法にありgenerateCombinationsRecursivelyます。
パラメータpositionは、再帰関数の深さに応じて可変です。positionパラメータの最大値は、combinationのリストサイズ（k）です。最大値（k）に達すると（メソッドの最初のブロックgenerateCombinationsRecursively）、結果のリストにnewcombinationが追加され、combinationList再帰が終了します。
メソッドの2番目のブロックは、リスト内のすべての要素を反復処理generateCombinationsRecursivelyするループです。値に応じて、リストには（T）の要素が入力されます。次に、再帰メソッド
が引数にアクセントを付けて呼び出されます。この引数は、の次の位置を指すようにインクリメントされ、その再帰メソッドには次の要素（Tから）が入力されます。forelementListpositioncombinationelementListgenerateCombinationsRecursivelypositioncombination
出力の組み合わせ：
[0, 0, 0]
[0, 0, 1]
[0, 1, 0]
[0, 1, 1]
[1, 0, 0]
[1, 0, 1]
[1, 1, 0]
[1, 1, 1]
combinationList結果のリストを出力します。
[[0, 0, 0], [0, 0, 1], [0, 1, 0], [0, 1, 1], [1, 0, 0], [1, 0, 1], [1, 1, 0], [1, 1, 1]]
于 2021-10-17T22:00:44.170 に答える