文字の配列を引数として取り、それらの文字の数を選択する関数を作成したいと思います。
8文字の配列を提供し、その中から3文字を選択するとします。次に、次のようになります。
8! / ((8 - 3)! * 3!) = 56
それぞれ3文字で構成される配列（または単語）。
522802 次
77 に答える
445
Art of Computer Programming Volume 4: Fascicle 3には、私が説明した方法よりも、特定の状況に適合する可能性があるこれらの機能がたくさんあります。
グレイコード
遭遇する問題はもちろんメモリであり、すぐに、セット内の 20 要素 ( 20 C 3 = 1140) で問題が発生します。セットを反復処理する場合は、修正されたグレーを使用するのが最善です。アルゴリズムをコード化して、それらすべてをメモリに保持しないようにします。これらは、前の組み合わせから次の組み合わせを生成し、繰り返しを回避します。さまざまな用途のために、これらの多くがあります。連続する組み合わせ間の差を最大化したいですか? 最小化しますか？など。
グレイコードを記述した元の論文のいくつか:
このトピックをカバーしている他の論文は次のとおりです。
- Eades、Hickey、Read Adjacent Interchange Combination Generation Algorithm (PDF、パスカルのコード付き)の効率的な実装
- コンビネーションジェネレーター
- 組み合わせグレイコードの調査(PostScript)
- グレイコードのアルゴリズム
チェイスのツイドル (アルゴリズム)
フィリップ J チェイス、「アルゴリズム 382: N オブジェクトからの M の組み合わせ」(1970)
Cのアルゴリズム...
辞書順の組み合わせのインデックス (Buckles Algorithm 515)
組み合わせをそのインデックス (辞書順) で参照することもできます。インデックスは、インデックスに基づいて右から左へのある程度の変化である必要があることを理解すると、組み合わせを回復する必要があるものを構築できます。
したがって、セット {1,2,3,4,5,6} があり、3 つの要素が必要です。{1,2,3} としましょう。要素間の違いは 1 で、順序が正しく、最小であると言えます。{1,2,4} には 1 つの変更があり、辞書編集的には 2 番目です。したがって、最後の場所の「変更」の数は、辞書編集順序の 1 つの変更を説明しています。1 つの変更がある 2 番目の場所 {1,3,4} には 1 つの変更がありますが、2 番目にあるため (元のセットの要素の数に比例)、より多くの変更が考慮されます。
私が説明した方法は、セットからインデックスへの分解であるように見えますが、その逆を行う必要があります。これは非常にトリッキーです。これが、バックルが問題を解決する方法です。それらを計算するためにいくつかの C を書きましたが、マイナーな変更が加えられています。セットを表すために数値範囲ではなくセットのインデックスを使用したため、常に 0...n から作業しています。ノート：
- 組み合わせは順不同であるため、{1,3,2} = {1,2,3} -- 辞書順に並べます。
- このメソッドには、最初の差分のセットを開始するための暗黙の 0 があります。
辞書順の組み合わせの索引 (McCaffrey)
別の方法があります:その概念は把握してプログラムするのが簡単ですが、バックルの最適化はありません. 幸いなことに、重複する組み合わせも生成されません。
を最大化するセット
、ここで
.
例: 27 = C(6,4) + C(5,3) + C(2,2) + C(1,1). したがって、4 つのものの 27 番目の辞書式の組み合わせは {1,2,5,6} です。これらは、見たいセットのインデックスです。以下の例 (OCaml) はchoose関数を必要とし、読者に任せます:
(* this will find the [x] combination of a [set] list when taking [k] elements *)
let combination_maccaffery set k x =
(* maximize function -- maximize a that is aCb *)
(* return largest c where c < i and choose(c,i) <= z *)
let rec maximize a b x =
if (choose a b ) <= x then a else maximize (a-1) b x
in
let rec iterate n x i = match i with
| 0 -> []
| i ->
let max = maximize n i x in
max :: iterate n (x - (choose max i)) (i-1)
in
if x < 0 then failwith "errors" else
let idxs = iterate (List.length set) x k in
List.map (List.nth set) (List.sort (-) idxs)
小さくて単純な組み合わせイテレータ
次の 2 つのアルゴリズムは、教訓的な目的で提供されています。これらは、反復子と (より一般的な) フォルダー全体の組み合わせを実装します。それらは可能な限り高速であり、複雑さは O( n C k ) です。メモリ消費量は によって制限されkます。
組み合わせごとにユーザー提供の関数を呼び出すイテレータから始めます。
let iter_combs n k f =
let rec iter v s j =
if j = k then f v
else for i = s to n - 1 do iter (i::v) (i+1) (j+1) done in
iter [] 0 0
より一般的なバージョンでは、初期状態から開始して、状態変数とともにユーザー提供の関数を呼び出します。異なる状態間で状態を渡す必要があるため、for ループは使用しませんが、代わりに再帰を使用します。
let fold_combs n k f x =
let rec loop i s c x =
if i < n then
loop (i+1) s c @@
let c = i::c and s = s + 1 and i = i + 1 in
if s < k then loop i s c x else f c x
else x in
loop 0 0 [] x
于 2008-09-24T15:24:50.300 に答える
206
C# の場合:
public static IEnumerable<IEnumerable<T>> Combinations<T>(this IEnumerable<T> elements, int k)
{
return k == 0 ? new[] { new T[0] } :
elements.SelectMany((e, i) =>
elements.Skip(i + 1).Combinations(k - 1).Select(c => (new[] {e}).Concat(c)));
}
使用法：
var result = Combinations(new[] { 1, 2, 3, 4, 5 }, 3);
結果：
123
124
125
134
135
145
234
235
245
345
于 2009-12-14T03:24:55.617 に答える
82
この問題に対する再帰的な Python ソリューションを提示してもよろしいですか?
def choose_iter(elements, length):
for i in xrange(len(elements)):
if length == 1:
yield (elements[i],)
else:
for next in choose_iter(elements[i+1:len(elements)], length-1):
yield (elements[i],) + next
def choose(l, k):
return list(choose_iter(l, k))
使用例:
>>> len(list(choose_iter("abcdefgh",3)))
56
そのシンプルさが気に入っています。
于 2010-05-14T21:15:34.873 に答える
70
文字の配列が「ABCDEFGH」のようになっているとしましょう。現在の単語に使用する文字を示す 3 つのインデックス (i、j、k) があります。
ABCDEFGH ^ ^ ^ ijk
最初に k を変化させるので、次のステップは次のようになります。
ABCDEFGH ^ ^ ^ ijk
終わりに達したら、j を変化させ、次に k を変化させます。
ABCDEFGH ^ ^ ^ ijk ABCDEFGH ^ ^ ^ ijk
j が G に達すると、i も変化し始めます。
ABCDEFGH ^ ^ ^ ijk ABCDEFGH ^ ^ ^ ijk ...
コードで書くとこんな感じ
void print_combinations(const char *string)
{
int i, j, k;
int len = strlen(string);
for (i = 0; i < len - 2; i++)
{
for (j = i + 1; j < len - 1; j++)
{
for (k = j + 1; k < len; k++)
printf("%c%c%c\n", string[i], string[j], string[k]);
}
}
}
于 2008-09-24T15:31:36.757 に答える
57
次の再帰的アルゴリズムは、順序集合からすべてのk要素の組み合わせを選択します。
i組み合わせの最初の要素を選択します- より大きい要素のセットから再帰的に選択された要素の組み合わせ
iのそれぞれと組み合わせます。k-1i
セット内のそれぞれについて上記を繰り返しiます。
i繰り返しを避けるために、残りの要素をより大きく選択することが重要です。このように、[3,5]は、[3]が[5]と組み合わされて、2回ではなく、1回だけ選択されます（条件によって[5] + [3]が削除されます）。この条件がないと、組み合わせではなくバリエーションが得られます。
于 2008-09-24T17:40:35.713 に答える
32
Python での短い例:
def comb(sofar, rest, n):
if n == 0:
print sofar
else:
for i in range(len(rest)):
comb(sofar + rest[i], rest[i+1:], n-1)
>>> comb("", "abcde", 3)
abc
abd
abe
acd
ace
ade
bcd
bce
bde
cde
説明のために、再帰的な方法を次の例で説明します。
例: ABCDE
3 のすべての組み合わせは次のようになります。
- 残りの 2 つのすべての組み合わせを持つ A (BCDE)
- 残りの 2 つのすべての組み合わせを含む B (CDE)
- 残りの 2 つのすべての組み合わせを含む C (DE)
于 2013-08-01T14:27:35.970 に答える
26
C++ では、次のルーチンは範囲 [first,last) の間の長さ distance(first,k) のすべての組み合わせを生成します。
#include <algorithm>
template <typename Iterator>
bool next_combination(const Iterator first, Iterator k, const Iterator last)
{
/* Credits: Mark Nelson http://marknelson.us */
if ((first == last) || (first == k) || (last == k))
return false;
Iterator i1 = first;
Iterator i2 = last;
++i1;
if (last == i1)
return false;
i1 = last;
--i1;
i1 = k;
--i2;
while (first != i1)
{
if (*--i1 < *i2)
{
Iterator j = k;
while (!(*i1 < *j)) ++j;
std::iter_swap(i1,j);
++i1;
++j;
i2 = k;
std::rotate(i1,j,last);
while (last != j)
{
++j;
++i2;
}
std::rotate(k,i2,last);
return true;
}
}
std::rotate(first,k,last);
return false;
}
次のように使用できます。
#include <string>
#include <iostream>
int main()
{
std::string s = "12345";
std::size_t comb_size = 3;
do
{
std::cout << std::string(s.begin(), s.begin() + comb_size) << std::endl;
} while (next_combination(s.begin(), s.begin() + comb_size, s.end()));
return 0;
}
これにより、次のように出力されます。
123
124
125
134
135
145
234
235
245
345
于 2009-10-24T11:58:21.873 に答える
26
このスレッドは役に立ち、Firebug にポップできる Javascript ソリューションを追加しようと考えました。JS エンジンによっては、開始文字列が大きい場合、少し時間がかかる場合があります。
function string_recurse(active, rest) {
if (rest.length == 0) {
console.log(active);
} else {
string_recurse(active + rest.charAt(0), rest.substring(1, rest.length));
string_recurse(active, rest.substring(1, rest.length));
}
}
string_recurse("", "abc");
出力は次のようになります。
abc
ab
ac
a
bc
b
c
于 2011-11-17T17:42:48.387 に答える
21
static IEnumerable<string> Combinations(List<string> characters, int length)
{
for (int i = 0; i < characters.Count; i++)
{
// only want 1 character, just return this one
if (length == 1)
yield return characters[i];
// want more than one character, return this one plus all combinations one shorter
// only use characters after the current one for the rest of the combinations
else
foreach (string next in Combinations(characters.GetRange(i + 1, characters.Count - (i + 1)), length - 1))
yield return characters[i] + next;
}
}
于 2008-09-24T15:37:26.807 に答える
20
Haskell の単純な再帰アルゴリズム
import Data.List
combinations 0 lst = [[]]
combinations n lst = do
(x:xs) <- tails lst
rest <- combinations (n-1) xs
return $ x : rest
最初に特殊なケースを定義します。つまり、ゼロ要素を選択します。これは、空のリスト (つまり、空のリストを含むリスト) である単一の結果を生成します。
n > 0の場合x、リストのすべての要素を通過し、 のxs後のすべての要素xです。
restへの再帰呼び出しを使用してn - 1要素を選択します。関数の最終結果は、 と の異なる値ごとに各要素が存在するリスト(つまり、頭と尾を持つリスト) です。xscombinationsx : restxrestxrest
> combinations 3 "abcde"
["abc","abd","abe","acd","ace","ade","bcd","bce","bde","cde"]
もちろん、Haskell は遅延型であるため、リストは必要に応じて徐々に生成されるため、指数関数的に大きな組み合わせを部分的に評価できます。
> let c = combinations 8 "abcdefghijklmnopqrstuvwxyz"
> take 10 c
["abcdefgh","abcdefgi","abcdefgj","abcdefgk","abcdefgl","abcdefgm","abcdefgn",
"abcdefgo","abcdefgp","abcdefgq"]
于 2011-12-24T17:49:38.670 に答える
14
そして、ここに、非常に悪意のある言語であるおじいちゃんCOBOLが登場します。
それぞれ8バイトの34要素の配列を想定します（純粋に任意の選択）。アイデアは、考えられるすべての4要素の組み合わせを列挙し、それらを配列にロードすることです。
4つのグループの各位置に1つずつ、合計4つのインデックスを使用します。
配列は次のように処理されます。
idx1 = 1
idx2 = 2
idx3 = 3
idx4 = 4
idx4を4から最後まで変化させます。idx4ごとに、4つのグループの一意の組み合わせを取得します。idx4が配列の最後に来ると、idx3を1インクリメントし、idx4をidx3+1に設定します。次に、idx4を最後まで実行します。このようにして、idx1の位置が配列の最後から4未満になるまで、それぞれidx3、idx2、およびidx1を拡張します。これでアルゴリズムは終了です。
1 --- pos.1
2 --- pos 2
3 --- pos 3
4 --- pos 4
5
6
7
etc.
最初の反復：
1234
1235
1236
1237
1245
1246
1247
1256
1257
1267
etc.
COBOLの例：
01 DATA_ARAY.
05 FILLER PIC X(8) VALUE "VALUE_01".
05 FILLER PIC X(8) VALUE "VALUE_02".
etc.
01 ARAY_DATA OCCURS 34.
05 ARAY_ITEM PIC X(8).
01 OUTPUT_ARAY OCCURS 50000 PIC X(32).
01 MAX_NUM PIC 99 COMP VALUE 34.
01 INDEXXES COMP.
05 IDX1 PIC 99.
05 IDX2 PIC 99.
05 IDX3 PIC 99.
05 IDX4 PIC 99.
05 OUT_IDX PIC 9(9).
01 WHERE_TO_STOP_SEARCH PIC 99 COMP.
* Stop the search when IDX1 is on the third last array element:
COMPUTE WHERE_TO_STOP_SEARCH = MAX_VALUE - 3
MOVE 1 TO IDX1
PERFORM UNTIL IDX1 > WHERE_TO_STOP_SEARCH
COMPUTE IDX2 = IDX1 + 1
PERFORM UNTIL IDX2 > MAX_NUM
COMPUTE IDX3 = IDX2 + 1
PERFORM UNTIL IDX3 > MAX_NUM
COMPUTE IDX4 = IDX3 + 1
PERFORM UNTIL IDX4 > MAX_NUM
ADD 1 TO OUT_IDX
STRING ARAY_ITEM(IDX1)
ARAY_ITEM(IDX2)
ARAY_ITEM(IDX3)
ARAY_ITEM(IDX4)
INTO OUTPUT_ARAY(OUT_IDX)
ADD 1 TO IDX4
END-PERFORM
ADD 1 TO IDX3
END-PERFORM
ADD 1 TO IDX2
END_PERFORM
ADD 1 TO IDX1
END-PERFORM.
于 2012-11-21T09:47:28.207 に答える
10
組み合わせインデックスの遅延生成を備えた別の C# バージョン。このバージョンは、すべての値のリストと現在の組み合わせの値との間のマッピングを定義するために、インデックスの単一の配列を維持します。つまり、ランタイム全体で常にO(k)の追加スペースを使用します。このコードは、最初の組み合わせを含む個々の組み合わせをO(k)時間で生成します。
public static IEnumerable<T[]> Combinations<T>(this T[] values, int k)
{
if (k < 0 || values.Length < k)
yield break; // invalid parameters, no combinations possible
// generate the initial combination indices
var combIndices = new int[k];
for (var i = 0; i < k; i++)
{
combIndices[i] = i;
}
while (true)
{
// return next combination
var combination = new T[k];
for (var i = 0; i < k; i++)
{
combination[i] = values[combIndices[i]];
}
yield return combination;
// find first index to update
var indexToUpdate = k - 1;
while (indexToUpdate >= 0 && combIndices[indexToUpdate] >= values.Length - k + indexToUpdate)
{
indexToUpdate--;
}
if (indexToUpdate < 0)
yield break; // done
// update combination indices
for (var combIndex = combIndices[indexToUpdate] + 1; indexToUpdate < k; indexToUpdate++, combIndex++)
{
combIndices[indexToUpdate] = combIndex;
}
}
}
テストコード:
foreach (var combination in new[] {'a', 'b', 'c', 'd', 'e'}.Combinations(3))
{
System.Console.WriteLine(String.Join(" ", combination));
}
出力：
a b c
a b d
a b e
a c d
a c e
a d e
b c d
b c e
b d e
c d e
于 2015-05-13T21:20:38.380 に答える
9
これは、 99 Scalaの問題 で説明されているように、Scalaでのエレガントで一般的な実装です。
object P26 {
def flatMapSublists[A,B](ls: List[A])(f: (List[A]) => List[B]): List[B] =
ls match {
case Nil => Nil
case sublist@(_ :: tail) => f(sublist) ::: flatMapSublists(tail)(f)
}
def combinations[A](n: Int, ls: List[A]): List[List[A]] =
if (n == 0) List(Nil)
else flatMapSublists(ls) { sl =>
combinations(n - 1, sl.tail) map {sl.head :: _}
}
}
于 2010-04-08T19:30:36.460 に答える
9
SQL 構文を使用できる場合 - たとえば、構造体または配列のフィールドにアクセスするために LINQ を使用している場合、または 1 つの char フィールド「Letter」を持つ「Alphabet」と呼ばれるテーブルを持つデータベースに直接アクセスしている場合、次のように適応できます。コード：
SELECT A.Letter, B.Letter, C.Letter
FROM Alphabet AS A, Alphabet AS B, Alphabet AS C
WHERE A.Letter<>B.Letter AND A.Letter<>C.Letter AND B.Letter<>C.Letter
AND A.Letter<B.Letter AND B.Letter<C.Letter
これは、テーブル「Alphabet」に含まれる文字数 (3、8、10、27 など) に関係なく、3 文字のすべての組み合わせを返します。
組み合わせではなくすべての順列が必要な場合 (つまり、"ACB" と "ABC" を 1 回だけ表示するのではなく、異なるものとしてカウントする場合) は、最後の行 (AND の行) を削除するだけで完了です。
事後編集: 質問を読み直した後、3 つの項目を選択する場合の特定のアルゴリズムだけでなく、一般的なアルゴリズムが必要であることがわかりました。Adam Hughes の答えは完全なものですが、残念ながら私はそれを投票することはできません (まだ)。この答えは単純ですが、ちょうど 3 つのアイテムが必要な場合にのみ機能します。
于 2008-09-24T16:59:58.683 に答える
8
Python でプロジェクト euler に使用した順列アルゴリズムがありました。
def missing(miss,src):
"Returns the list of items in src not present in miss"
return [i for i in src if i not in miss]
def permutation_gen(n,l):
"Generates all the permutations of n items of the l list"
for i in l:
if n<=1: yield [i]
r = [i]
for j in permutation_gen(n-1,missing([i],l)): yield r+j
もしも
n<len(l)
繰り返しなしで必要なすべての組み合わせが必要ですが、必要ですか?
これはジェネレーターなので、次のように使用します。
for comb in permutation_gen(3,list("ABCDEFGH")):
print comb
于 2008-09-25T07:13:00.783 に答える
7
https://gist.github.com/3118596
JavaScript の実装があります。k-組み合わせと任意のオブジェクトの配列のすべての組み合わせを取得する関数があります。例:
k_combinations([1,2,3], 2)
-> [[1,2], [1,3], [2,3]]
combinations([1,2,3])
-> [[1],[2],[3],[1,2],[1,3],[2,3],[1,2,3]]
于 2012-07-15T21:05:57.150 に答える
6
ここに、C# でコーディングされたそのアルゴリズムの遅延評価バージョンがあります。
static bool nextCombination(int[] num, int n, int k)
{
bool finished, changed;
changed = finished = false;
if (k > 0)
{
for (int i = k - 1; !finished && !changed; i--)
{
if (num[i] < (n - 1) - (k - 1) + i)
{
num[i]++;
if (i < k - 1)
{
for (int j = i + 1; j < k; j++)
{
num[j] = num[j - 1] + 1;
}
}
changed = true;
}
finished = (i == 0);
}
}
return changed;
}
static IEnumerable Combinations<T>(IEnumerable<T> elements, int k)
{
T[] elem = elements.ToArray();
int size = elem.Length;
if (k <= size)
{
int[] numbers = new int[k];
for (int i = 0; i < k; i++)
{
numbers[i] = i;
}
do
{
yield return numbers.Select(n => elem[n]);
}
while (nextCombination(numbers, size, k));
}
}
そしてテスト部分：
static void Main(string[] args)
{
int k = 3;
var t = new[] { "dog", "cat", "mouse", "zebra"};
foreach (IEnumerable<string> i in Combinations(t, k))
{
Console.WriteLine(string.Join(",", i));
}
}
これがあなたを助けることを願っています!
于 2010-12-26T18:43:05.860 に答える
5
Array.prototype.combs = function(num) {
var str = this,
length = str.length,
of = Math.pow(2, length) - 1,
out, combinations = [];
while(of) {
out = [];
for(var i = 0, y; i < length; i++) {
y = (1 << i);
if(y & of && (y !== of))
out.push(str[i]);
}
if (out.length >= num) {
combinations.push(out);
}
of--;
}
return combinations;
}
于 2012-05-21T18:53:51.963 に答える
5
Clojure のバージョン:
(defn comb [k l]
(if (= 1 k) (map vector l)
(apply concat
(map-indexed
#(map (fn [x] (conj x %2))
(comb (dec k) (drop (inc %1) l)))
l))))
于 2014-01-04T03:56:13.673 に答える
4
以上が、そのための O'caml コードです。アルゴリズムはコードから明らかです。
let combi n lst =
let rec comb l c =
if( List.length c = n) then [c] else
match l with
[] -> []
| (h::t) -> (combi t (h::c))@(combi t c)
in
combi lst []
;;
于 2014-03-03T13:52:52.970 に答える
4
これは、ランダムな長さの文字列から指定されたサイズのすべての組み合わせを提供する方法です。quinmars のソリューションに似ていますが、さまざまな入力と k に対して機能します。
コードはラップアラウンドに変更できます。つまり、入力 'abcd' wk=3 から 'dab' に変更できます。
public void run(String data, int howMany){
choose(data, howMany, new StringBuffer(), 0);
}
//n choose k
private void choose(String data, int k, StringBuffer result, int startIndex){
if (result.length()==k){
System.out.println(result.toString());
return;
}
for (int i=startIndex; i<data.length(); i++){
result.append(data.charAt(i));
choose(data,k,result, i+1);
result.setLength(result.length()-1);
}
}
「abcde」の出力:
abc abd abe acd ace ade bcd bce bde cde
于 2011-12-13T20:20:33.953 に答える
3
これがC++での私の提案です
イテレーターのタイプにできるだけ制限を課さないようにしたので、このソリューションはフォワードイテレーターのみを想定しており、const_iteratorにすることができます。これは、標準のコンテナで機能するはずです。引数が意味をなさない場合は、std::invalid_argumnentをスローします
#include <vector>
#include <stdexcept>
template <typename Fci> // Fci - forward const iterator
std::vector<std::vector<Fci> >
enumerate_combinations(Fci begin, Fci end, unsigned int combination_size)
{
if(begin == end && combination_size > 0u)
throw std::invalid_argument("empty set and positive combination size!");
std::vector<std::vector<Fci> > result; // empty set of combinations
if(combination_size == 0u) return result; // there is exactly one combination of
// size 0 - emty set
std::vector<Fci> current_combination;
current_combination.reserve(combination_size + 1u); // I reserve one aditional slot
// in my vector to store
// the end sentinel there.
// The code is cleaner thanks to that
for(unsigned int i = 0u; i < combination_size && begin != end; ++i, ++begin)
{
current_combination.push_back(begin); // Construction of the first combination
}
// Since I assume the itarators support only incrementing, I have to iterate over
// the set to get its size, which is expensive. Here I had to itrate anyway to
// produce the first cobination, so I use the loop to also check the size.
if(current_combination.size() < combination_size)
throw std::invalid_argument("combination size > set size!");
result.push_back(current_combination); // Store the first combination in the results set
current_combination.push_back(end); // Here I add mentioned earlier sentinel to
// simplyfy rest of the code. If I did it
// earlier, previous statement would get ugly.
while(true)
{
unsigned int i = combination_size;
Fci tmp; // Thanks to the sentinel I can find first
do // iterator to change, simply by scaning
{ // from right to left and looking for the
tmp = current_combination[--i]; // first "bubble". The fact, that it's
++tmp; // a forward iterator makes it ugly but I
} // can't help it.
while(i > 0u && tmp == current_combination[i + 1u]);
// Here is probably my most obfuscated expression.
// Loop above looks for a "bubble". If there is no "bubble", that means, that
// current_combination is the last combination, Expression in the if statement
// below evaluates to true and the function exits returning result.
// If the "bubble" is found however, the ststement below has a sideeffect of
// incrementing the first iterator to the left of the "bubble".
if(++current_combination[i] == current_combination[i + 1u])
return result;
// Rest of the code sets posiotons of the rest of the iterstors
// (if there are any), that are to the right of the incremented one,
// to form next combination
while(++i < combination_size)
{
current_combination[i] = current_combination[i - 1u];
++current_combination[i];
}
// Below is the ugly side of using the sentinel. Well it had to haave some
// disadvantage. Try without it.
result.push_back(std::vector<Fci>(current_combination.begin(),
current_combination.end() - 1));
}
}
于 2008-09-25T07:00:54.120 に答える
3
これは私が最近Javaで書いたコードで、「outOf」要素から「num」要素のすべての組み合わせを計算して返します。
// author: Sourabh Bhat (heySourabh@gmail.com)
public class Testing
{
public static void main(String[] args)
{
// Test case num = 5, outOf = 8.
int num = 5;
int outOf = 8;
int[][] combinations = getCombinations(num, outOf);
for (int i = 0; i < combinations.length; i++)
{
for (int j = 0; j < combinations[i].length; j++)
{
System.out.print(combinations[i][j] + " ");
}
System.out.println();
}
}
private static int[][] getCombinations(int num, int outOf)
{
int possibilities = get_nCr(outOf, num);
int[][] combinations = new int[possibilities][num];
int arrayPointer = 0;
int[] counter = new int[num];
for (int i = 0; i < num; i++)
{
counter[i] = i;
}
breakLoop: while (true)
{
// Initializing part
for (int i = 1; i < num; i++)
{
if (counter[i] >= outOf - (num - 1 - i))
counter[i] = counter[i - 1] + 1;
}
// Testing part
for (int i = 0; i < num; i++)
{
if (counter[i] < outOf)
{
continue;
} else
{
break breakLoop;
}
}
// Innermost part
combinations[arrayPointer] = counter.clone();
arrayPointer++;
// Incrementing part
counter[num - 1]++;
for (int i = num - 1; i >= 1; i--)
{
if (counter[i] >= outOf - (num - 1 - i))
counter[i - 1]++;
}
}
return combinations;
}
private static int get_nCr(int n, int r)
{
if(r > n)
{
throw new ArithmeticException("r is greater then n");
}
long numerator = 1;
long denominator = 1;
for (int i = n; i >= r + 1; i--)
{
numerator *= i;
}
for (int i = 2; i <= n - r; i++)
{
denominator *= i;
}
return (int) (numerator / denominator);
}
}
于 2010-03-13T13:10:35.313 に答える
3
簡潔な Javascript ソリューション:
Array.prototype.combine=function combine(k){
var toCombine=this;
var last;
function combi(n,comb){
var combs=[];
for ( var x=0,y=comb.length;x<y;x++){
for ( var l=0,m=toCombine.length;l<m;l++){
combs.push(comb[x]+toCombine[l]);
}
}
if (n<k-1){
n++;
combi(n,combs);
} else{last=combs;}
}
combi(1,toCombine);
return last;
}
// Example:
// var toCombine=['a','b','c'];
// var results=toCombine.combine(4);
于 2014-09-26T12:52:15.157 に答える
3
インデックス位置を生成する短い python コード
def yield_combos(n,k):
# n is set size, k is combo size
i = 0
a = [0]*k
while i > -1:
for j in range(i+1, k):
a[j] = a[j-1]+1
i=j
yield a
while a[i] == i + n - k:
i -= 1
a[i] += 1
于 2015-04-18T10:21:56.683 に答える
3
このためのソリューションを SQL Server 2005 で作成し、Web サイトに投稿しました: http://www.jessemclain.com/downloads/code/sql/fn_GetMChooseNCombos.sql.htm
使用法を示す例を次に示します。
SELECT * FROM dbo.fn_GetMChooseNCombos('ABCD', 2, '')
結果：
Word
----
AB
AC
AD
BC
BD
CD
(6 row(s) affected)
于 2009-06-30T14:48:02.657 に答える
2
問題が該当するタイプの問題である二項係数を操作するための一般的な関数を処理するクラスを作成しました。次のタスクを実行します。
すべてのKインデックスを、任意のN選択Kのファイルに適切な形式で出力します。Kインデックスは、より説明的な文字列または文字に置き換えることができます。この方法では、このタイプの問題を簡単に解決できます。
Kインデックスを、ソートされた二項係数テーブルのエントリの適切なインデックスに変換します。この手法は、反復に依存する以前に公開された手法よりもはるかに高速です。これは、パスカルの三角形に固有の数学的プロパティを使用して行われます。私の論文はこれについて話します。私はこのテクニックを最初に発見して公開したと思いますが、間違っている可能性があります。
ソートされた二項係数テーブルのインデックスを対応するKインデックスに変換します。
マークドミナス法を使用して二項係数を計算します。二項係数はオーバーフローする可能性がはるかに低く、より大きな数値で機能します。
このクラスは.NETC＃で記述されており、ジェネリックリストを使用して問題に関連するオブジェクト（存在する場合）を管理する方法を提供します。このクラスのコンストラクターは、InitTableと呼ばれるbool値を取ります。これは、trueの場合、管理対象のオブジェクトを保持するためのジェネリックリストを作成します。この値がfalseの場合、テーブルは作成されません。上記の4つの方法を実行するために、テーブルを作成する必要はありません。テーブルにアクセスするためのアクセサメソッドが提供されています。
クラスとそのメソッドの使用方法を示す関連するテストクラスがあります。2つのケースで広範囲にテストされており、既知のバグはありません。
このクラスについて読んでコードをダウンロードするには、二項係数の表化を参照してください。
このクラスをC++に変換するのは難しいことではありません。
于 2012-09-25T07:49:04.030 に答える
2
The Art of Computer Programming, Volume 4A: Combinatorial Algorithms, Part 1 の セクション 7.2.1.3 の Algorithm L (辞書式の組み合わせ) の C コード:
#include <stdio.h>
#include <stdlib.h>
void visit(int* c, int t)
{
// for (int j = 1; j <= t; j++)
for (int j = t; j > 0; j--)
printf("%d ", c[j]);
printf("\n");
}
int* initialize(int n, int t)
{
// c[0] not used
int *c = (int*) malloc((t + 3) * sizeof(int));
for (int j = 1; j <= t; j++)
c[j] = j - 1;
c[t+1] = n;
c[t+2] = 0;
return c;
}
void comb(int n, int t)
{
int *c = initialize(n, t);
int j;
for (;;) {
visit(c, t);
j = 1;
while (c[j]+1 == c[j+1]) {
c[j] = j - 1;
++j;
}
if (j > t)
return;
++c[j];
}
free(c);
}
int main(int argc, char *argv[])
{
comb(5, 3);
return 0;
}
于 2015-12-26T15:14:58.273 に答える
2
時流に乗って、別の解決策を投稿します。これは一般的な Java 実装です。入力:(int k)選択する要素の数であり、選択(List<T> list)するリストです。組み合わせのリストを返します(List<List<T>>)。
public static <T> List<List<T>> getCombinations(int k, List<T> list) {
List<List<T>> combinations = new ArrayList<List<T>>();
if (k == 0) {
combinations.add(new ArrayList<T>());
return combinations;
}
for (int i = 0; i < list.size(); i++) {
T element = list.get(i);
List<T> rest = getSublist(list, i+1);
for (List<T> previous : getCombinations(k-1, rest)) {
previous.add(element);
combinations.add(previous);
}
}
return combinations;
}
public static <T> List<T> getSublist(List<T> list, int i) {
List<T> sublist = new ArrayList<T>();
for (int j = i; j < list.size(); j++) {
sublist.add(list.get(j));
}
return sublist;
}
于 2016-01-04T09:48:47.987 に答える
2
これは、ほぼすべての変数を排除するreduce / mapを使用することで、もう少し機能的な私のJavaScriptソリューションです
function combinations(arr, size) {
var len = arr.length;
if (size > len) return [];
if (!size) return [[]];
if (size == len) return [arr];
return arr.reduce(function (acc, val, i) {
var res = combinations(arr.slice(i + 1), size - 1)
.map(function (comb) { return [val].concat(comb); });
return acc.concat(res);
}, []);
}
var combs = combinations([1,2,3,4,5,6,7,8],3);
combs.map(function (comb) {
document.body.innerHTML += comb.toString() + '<br />';
});
document.body.innerHTML += '<br /> Total combinations = ' + combs.length;于 2015-05-16T17:44:19.743 に答える
1
#include <stdio.h>
unsigned int next_combination(unsigned int *ar, size_t n, unsigned int k)
{
unsigned int finished = 0;
unsigned int changed = 0;
unsigned int i;
if (k > 0) {
for (i = k - 1; !finished && !changed; i--) {
if (ar[i] < (n - 1) - (k - 1) + i) {
/* Increment this element */
ar[i]++;
if (i < k - 1) {
/* Turn the elements after it into a linear sequence */
unsigned int j;
for (j = i + 1; j < k; j++) {
ar[j] = ar[j - 1] + 1;
}
}
changed = 1;
}
finished = i == 0;
}
if (!changed) {
/* Reset to first combination */
for (i = 0; i < k; i++) {
ar[i] = i;
}
}
}
return changed;
}
typedef void(*printfn)(const void *, FILE *);
void print_set(const unsigned int *ar, size_t len, const void **elements,
const char *brackets, printfn print, FILE *fptr)
{
unsigned int i;
fputc(brackets[0], fptr);
for (i = 0; i < len; i++) {
print(elements[ar[i]], fptr);
if (i < len - 1) {
fputs(", ", fptr);
}
}
fputc(brackets[1], fptr);
}
int main(void)
{
unsigned int numbers[] = { 0, 1, 2 };
char *elements[] = { "a", "b", "c", "d", "e" };
const unsigned int k = sizeof(numbers) / sizeof(unsigned int);
const unsigned int n = sizeof(elements) / sizeof(const char*);
do {
print_set(numbers, k, (void*)elements, "[]", (printfn)fputs, stdout);
putchar('\n');
} while (next_combination(numbers, n, k));
getchar();
return 0;
}
于 2013-07-14T12:19:34.560 に答える
1
これが私のScalaソリューションです:
def combinations[A](s: List[A], k: Int): List[List[A]] =
if (k > s.length) Nil
else if (k == 1) s.map(List(_))
else combinations(s.tail, k - 1).map(s.head :: _) ::: combinations(s.tail, k)
于 2013-07-04T15:59:57.370 に答える
1
void combine(char a[], int N, int M, int m, int start, char result[]) {
if (0 == m) {
for (int i = M - 1; i >= 0; i--)
std::cout << result[i];
std::cout << std::endl;
return;
}
for (int i = start; i < (N - m + 1); i++) {
result[m - 1] = a[i];
combine(a, N, M, m-1, i+1, result);
}
}
void combine(char a[], int N, int M) {
char *result = new char[M];
combine(a, N, M, M, 0, result);
delete[] result;
}
最初の関数で、 m はあと何個選択する必要があるかを示し、 start は配列内のどの位置から選択を開始する必要があるかを示します。
于 2012-07-22T19:32:43.847 に答える
1
プログラミング言語については言及されていないので、リストも問題ないと思います。そこで、短いリスト (非末尾再帰) に適した OCaml バージョンを次に示します。任意の型の要素のリストlと整数nを指定すると、結果リスト内の要素の順序が無視されると仮定すると、lのn 個の要素を含むすべての可能なリストのリストが返されます。つまり、リスト ['a'; 'b'] は ['b';'a'] と同じで、1 回報告されます。したがって、結果のリストのサイズは ((List.length l) Choose n) になります。
再帰の直感は次のとおりです。リストの先頭を取得してから、2 つの再帰呼び出しを行います。
- 再帰呼び出し 1 (RC1): リストの最後に、ただし n-1 個の要素を選択します
- 再帰呼び出し 2 (RC2): リストの最後に、ただし n 個の要素を選択します
再帰的な結果を結合するには、リストの先頭に RC1 の結果をリスト乗算 (奇妙な名前を付けてください) し、RC2 の結果を追加 (@) します。リスト乗算は次の操作lmulです。
a lmul [ l1 ; l2 ; l3] = [a::l1 ; a::l2 ; a::l3]
lmul以下のコードで実装されています
List.map (fun x -> h::x)
リストのサイズが選択したい要素の数と等しくなると、再帰は終了します。この場合、リスト自体を返すだけです。
上記のアルゴリズムを実装する OCaml の 4 ライナーは次のとおりです。
let rec choose l n = match l, (List.length l) with
| _, lsize when n==lsize -> [l]
| h::t, _ -> (List.map (fun x-> h::x) (choose t (n-1))) @ (choose t n)
| [], _ -> []
于 2012-03-15T19:05:33.060 に答える
1
そして、 OCaml実装の回答で説明したのと同じアルゴリズムを使用するClojureバージョンを次に示します。
(defn select
([items]
(select items 0 (inc (count items))))
([items n1 n2]
(reduce concat
(map #(select % items)
(range n1 (inc n2)))))
([n items]
(let [
lmul (fn [a list-of-lists-of-bs]
(map #(cons a %) list-of-lists-of-bs))
]
(if (= n (count items))
(list items)
(if (empty? items)
items
(concat
(select n (rest items))
(lmul (first items) (select (dec n) (rest items)))))))))
それを呼び出すには、次の 3 つの方法があります。
（a）質問が要求するように、正確にn個の選択されたアイテムに対して：
user=> (count (select 3 "abcdefgh"))
56
(b) n1からn2の選択された項目の場合:
user=> (select '(1 2 3 4) 2 3)
((3 4) (2 4) (2 3) (1 4) (1 3) (1 2) (2 3 4) (1 3 4) (1 2 4) (1 2 3))
(c) 0から選択されたコレクションのサイズの場合:
user=> (select '(1 2 3))
(() (3) (2) (1) (2 3) (1 3) (1 2) (1 2 3))
于 2013-02-11T21:17:11.633 に答える
1
Lisp マクロは、すべての値 r のコードを生成します (一度に取得)
(defmacro txaat (some-list taken-at-a-time)
(let* ((vars (reverse (truncate-list '(a b c d e f g h i j) taken-at-a-time))))
`(
,@(loop for i below taken-at-a-time
for j in vars
with nested = nil
finally (return nested)
do
(setf
nested
`(loop for ,j from
,(if (< i (1- (length vars)))
`(1+ ,(nth (1+ i) vars))
0)
below (- (length ,some-list) ,i)
,@(if (equal i 0)
`(collect
(list
,@(loop for k from (1- taken-at-a-time) downto 0
append `((nth ,(nth k vars) ,some-list)))))
`(append ,nested))))))))
そう、
CL-USER> (macroexpand-1 '(txaat '(a b c d) 1))
(LOOP FOR A FROM 0 TO (- (LENGTH '(A B C D)) 1)
COLLECT (LIST (NTH A '(A B C D))))
T
CL-USER> (macroexpand-1 '(txaat '(a b c d) 2))
(LOOP FOR A FROM 0 TO (- (LENGTH '(A B C D)) 2)
APPEND (LOOP FOR B FROM (1+ A) TO (- (LENGTH '(A B C D)) 1)
COLLECT (LIST (NTH A '(A B C D)) (NTH B '(A B C D)))))
T
CL-USER> (macroexpand-1 '(txaat '(a b c d) 3))
(LOOP FOR A FROM 0 TO (- (LENGTH '(A B C D)) 3)
APPEND (LOOP FOR B FROM (1+ A) TO (- (LENGTH '(A B C D)) 2)
APPEND (LOOP FOR C FROM (1+ B) TO (- (LENGTH '(A B C D)) 1)
COLLECT (LIST (NTH A '(A B C D))
(NTH B '(A B C D))
(NTH C '(A B C D))))))
T
CL-USER>
と、
CL-USER> (txaat '(a b c d) 1)
((A) (B) (C) (D))
CL-USER> (txaat '(a b c d) 2)
((A B) (A C) (A D) (B C) (B D) (C D))
CL-USER> (txaat '(a b c d) 3)
((A B C) (A B D) (A C D) (B C D))
CL-USER> (txaat '(a b c d) 4)
((A B C D))
CL-USER> (txaat '(a b c d) 5)
NIL
CL-USER> (txaat '(a b c d) 0)
NIL
CL-USER>
于 2011-07-17T15:41:04.860 に答える
1
すべての C(n,m) の組み合わせを出力する簡単なコードを次に示します。次の有効な組み合わせを指す一連の配列インデックスを初期化して移動することで機能します。インデックスは、最小の m 個のインデックス (辞書編集的に最小の組み合わせ) を指すように初期化されます。次に、m 番目のインデックスから始めて、インデックスを前方に移動しようとします。インデックスが限界に達した場合は、前のインデックス (インデックス 1 まで) を試します。インデックスを前方に移動できる場合は、それより大きなインデックスをすべてリセットします。
m=(rand()%n)+1; // m will vary from 1 to n
for (i=0;i<n;i++) a[i]=i+1;
// we want to print all possible C(n,m) combinations of selecting m objects out of n
printf("Printing C(%d,%d) possible combinations ...\n", n,m);
// This is an adhoc algo that keeps m pointers to the next valid combination
for (i=0;i<m;i++) p[i]=i; // the p[.] contain indices to the a vector whose elements constitute next combination
done=false;
while (!done)
{
// print combination
for (i=0;i<m;i++) printf("%2d ", a[p[i]]);
printf("\n");
// update combination
// method: start with p[m-1]. try to increment it. if it is already at the end, then try moving p[m-2] ahead.
// if this is possible, then reset p[m-1] to 1 more than (the new) p[m-2].
// if p[m-2] can not also be moved, then try p[m-3]. move that ahead. then reset p[m-2] and p[m-1].
// repeat all the way down to p[0]. if p[0] can not also be moved, then we have generated all combinations.
j=m-1;
i=1;
move_found=false;
while ((j>=0) && !move_found)
{
if (p[j]<(n-i))
{
move_found=true;
p[j]++; // point p[j] to next index
for (k=j+1;k<m;k++)
{
p[k]=p[j]+(k-j);
}
}
else
{
j--;
i++;
}
}
if (!move_found) done=true;
}
于 2010-04-06T09:18:17.670 に答える
1
nCk.Elementsこれは、 in collection が from 1toであると想定さ
れる組み合わせを生成する再帰的なプログラムです。n
#include<stdio.h>
#include<stdlib.h>
int nCk(int n,int loopno,int ini,int *a,int k)
{
static int count=0;
int i;
loopno--;
if(loopno<0)
{
a[k-1]=ini;
for(i=0;i<k;i++)
{
printf("%d,",a[i]);
}
printf("\n");
count++;
return 0;
}
for(i=ini;i<=n-loopno-1;i++)
{
a[k-1-loopno]=i+1;
nCk(n,loopno,i+1,a,k);
}
if(ini==0)
return count;
else
return 0;
}
void main()
{
int n,k,*a,count;
printf("Enter the value of n and k\n");
scanf("%d %d",&n,&k);
a=(int*)malloc(k*sizeof(int));
count=nCk(n,k,0,a,k);
printf("No of combinations=%d\n",count);
}
于 2012-01-20T19:26:06.900 に答える
1
VB.Net では、このアルゴリズムは一連の数値 (PoolArray) から n 個の数値のすべての組み合わせを収集します。たとえば、「8,10,20,33,41,44,47」から 5 つのピックのすべての組み合わせ。
Sub CreateAllCombinationsOfPicksFromPool(ByVal PicksArray() As UInteger, ByVal PicksIndex As UInteger, ByVal PoolArray() As UInteger, ByVal PoolIndex As UInteger)
If PicksIndex < PicksArray.Length Then
For i As Integer = PoolIndex To PoolArray.Length - PicksArray.Length + PicksIndex
PicksArray(PicksIndex) = PoolArray(i)
CreateAllCombinationsOfPicksFromPool(PicksArray, PicksIndex + 1, PoolArray, i + 1)
Next
Else
' completed combination. build your collections using PicksArray.
End If
End Sub
Dim PoolArray() As UInteger = Array.ConvertAll("8,10,20,33,41,44,47".Split(","), Function(u) UInteger.Parse(u))
Dim nPicks as UInteger = 5
Dim Picks(nPicks - 1) As UInteger
CreateAllCombinationsOfPicksFromPool(Picks, 0, PoolArray, 0)
于 2012-01-24T11:41:29.623 に答える
0
さらに別の再帰的な解決策 (数字の代わりに文字を使用するようにこれを移植できるはずです) スタックを使用しますが、ほとんどの場合よりも少し短くなります:
stack = []
def choose(n,x):
r(0,0,n+1,x)
def r(p, c, n,x):
if x-c == 0:
print stack
return
for i in range(p, n-(x-1)+c):
stack.append(i)
r(i+1,c+1,n,x)
stack.pop()
4 3 を選択するか、0 から 4 で始まる数字の 3 つの組み合わせすべてが必要です
choose(4,3)
[0, 1, 2]
[0, 1, 3]
[0, 1, 4]
[0, 2, 3]
[0, 2, 4]
[0, 3, 4]
[1, 2, 3]
[1, 2, 4]
[1, 3, 4]
[2, 3, 4]
于 2013-05-12T06:46:26.670 に答える
0
シンプルだが遅い C++ バックトラッキング アルゴリズム。
#include <iostream>
void backtrack(int* numbers, int n, int k, int i, int s)
{
if (i == k)
{
for (int j = 0; j < k; ++j)
{
std::cout << numbers[j];
}
std::cout << std::endl;
return;
}
if (s > n)
{
return;
}
numbers[i] = s;
backtrack(numbers, n, k, i + 1, s + 1);
backtrack(numbers, n, k, i, s + 1);
}
int main(int argc, char* argv[])
{
int n = 5;
int k = 3;
int* numbers = new int[k];
backtrack(numbers, n, k, 0, 1);
delete[] numbers;
return 0;
}
于 2017-01-03T13:26:52.877 に答える
0
これは、再帰とビットシフトを使用して思いついたC++ソリューションです。C でも動作する可能性があります。
void r_nCr(unsigned int startNum, unsigned int bitVal, unsigned int testNum) // Should be called with arguments (2^r)-1, 2^(r-1), 2^(n-1)
{
unsigned int n = (startNum - bitVal) << 1;
n += bitVal ? 1 : 0;
for (unsigned int i = log2(testNum) + 1; i > 0; i--) // Prints combination as a series of 1s and 0s
cout << (n >> (i - 1) & 1);
cout << endl;
if (!(n & testNum) && n != startNum)
r_nCr(n, bitVal, testNum);
if (bitVal && bitVal < testNum)
r_nCr(startNum, bitVal >> 1, testNum);
}
これがどのように機能するかについての説明は、こちらでご覧いただけます。
于 2014-12-05T08:23:08.507 に答える
0
短い高速 C# 実装
public static IEnumerable<IEnumerable<T>> Combinations<T>(IEnumerable<T> elements, int k)
{
return Combinations(elements.Count(), k).Select(p => p.Select(q => elements.ElementAt(q)));
}
public static List<int[]> Combinations(int setLenght, int subSetLenght) //5, 3
{
var result = new List<int[]>();
var lastIndex = subSetLenght - 1;
var dif = setLenght - subSetLenght;
var prevSubSet = new int[subSetLenght];
var lastSubSet = new int[subSetLenght];
for (int i = 0; i < subSetLenght; i++)
{
prevSubSet[i] = i;
lastSubSet[i] = i + dif;
}
while(true)
{
//add subSet ad result set
var n = new int[subSetLenght];
for (int i = 0; i < subSetLenght; i++)
n[i] = prevSubSet[i];
result.Add(n);
if (prevSubSet[0] >= lastSubSet[0])
break;
//start at index 1 because index 0 is checked and breaking in the current loop
int j = 1;
for (; j < subSetLenght; j++)
{
if (prevSubSet[j] >= lastSubSet[j])
{
prevSubSet[j - 1]++;
for (int p = j; p < subSetLenght; p++)
prevSubSet[p] = prevSubSet[p - 1] + 1;
break;
}
}
if (j > lastIndex)
prevSubSet[lastIndex]++;
}
return result;
}
于 2014-06-28T13:24:33.843 に答える
0
短い高速 C 実装
#include <stdio.h>
void main(int argc, char *argv[]) {
const int n = 6; /* The size of the set; for {1, 2, 3, 4} it's 4 */
const int p = 4; /* The size of the subsets; for {1, 2}, {1, 3}, ... it's 2 */
int comb[40] = {0}; /* comb[i] is the index of the i-th element in the combination */
int i = 0;
for (int j = 0; j <= n; j++) comb[j] = 0;
while (i >= 0) {
if (comb[i] < n + i - p + 1) {
comb[i]++;
if (i == p - 1) { for (int j = 0; j < p; j++) printf("%d ", comb[j]); printf("\n"); }
else { comb[++i] = comb[i - 1]; }
} else i--; }
}
速度を確認するには、このコードを使用してテストします
#include <time.h>
#include <stdio.h>
void main(int argc, char *argv[]) {
const int n = 32; /* The size of the set; for {1, 2, 3, 4} it's 4 */
const int p = 16; /* The size of the subsets; for {1, 2}, {1, 3}, ... it's 2 */
int comb[40] = {0}; /* comb[i] is the index of the i-th element in the combination */
int c = 0; int i = 0;
for (int j = 0; j <= n; j++) comb[j] = 0;
while (i >= 0) {
if (comb[i] < n + i - p + 1) {
comb[i]++;
/* if (i == p - 1) { for (int j = 0; j < p; j++) printf("%d ", comb[j]); printf("\n"); } */
if (i == p - 1) c++;
else { comb[++i] = comb[i - 1]; }
} else i--; }
printf("%d!%d == %d combination(s) in %15.3f second(s)\n ", p, n, c, clock()/1000.0);
}
cmd.exe でテストします (Windows):
Microsoft Windows XP [Version 5.1.2600]
(C) Copyright 1985-2001 Microsoft Corp.
c:\Program Files\lcc\projects>combination
16!32 == 601080390 combination(s) in 5.781 second(s)
c:\Program Files\lcc\projects>
良い１日を。
于 2013-04-27T15:33:21.040 に答える
0
これは、この問題を解決するために私が思いついたアルゴリズムです。C++ で書かれていますが、ビット演算をサポートするほとんどすべての言語に適応できます。
void r_nCr(const unsigned int &startNum, const unsigned int &bitVal, const unsigned int &testNum) // Should be called with arguments (2^r)-1, 2^(r-1), 2^(n-1)
{
unsigned int n = (startNum - bitVal) << 1;
n += bitVal ? 1 : 0;
for (unsigned int i = log2(testNum) + 1; i > 0; i--) // Prints combination as a series of 1s and 0s
cout << (n >> (i - 1) & 1);
cout << endl;
if (!(n & testNum) && n != startNum)
r_nCr(n, bitVal, testNum);
if (bitVal && bitVal < testNum)
r_nCr(startNum, bitVal >> 1, testNum);
}
仕組みの説明はこちらでご覧いただけます。
于 2015-02-03T19:48:26.587 に答える
0
Python では Andrea Ambu と同様ですが、3 つを選択するためにハードコーディングされていません。
def combinations(list, k):
"""Choose combinations of list, choosing k elements(no repeats)"""
if len(list) < k:
return []
else:
seq = [i for i in range(k)]
while seq:
print [list[index] for index in seq]
seq = get_next_combination(len(list), k, seq)
def get_next_combination(num_elements, k, seq):
index_to_move = find_index_to_move(num_elements, seq)
if index_to_move == None:
return None
else:
seq[index_to_move] += 1
#for every element past this sequence, move it down
for i, elem in enumerate(seq[(index_to_move+1):]):
seq[i + 1 + index_to_move] = seq[index_to_move] + i + 1
return seq
def find_index_to_move(num_elements, seq):
"""Tells which index should be moved"""
for rev_index, elem in enumerate(reversed(seq)):
if elem < (num_elements - rev_index - 1):
return len(seq) - rev_index - 1
return None
于 2008-12-04T00:02:09.517 に答える
0
この答えはどうですか...これは長さ3のすべての組み合わせを出力します...そして、任意の長さで一般化できます...作業コード...
#include<iostream>
#include<string>
using namespace std;
void combination(string a,string dest){
int l = dest.length();
if(a.empty() && l == 3 ){
cout<<dest<<endl;}
else{
if(!a.empty() && dest.length() < 3 ){
combination(a.substr(1,a.length()),dest+a[0]);}
if(!a.empty() && dest.length() <= 3 ){
combination(a.substr(1,a.length()),dest);}
}
}
int main(){
string demo("abcd");
combination(demo,"");
return 0;
}
于 2013-01-12T09:52:11.507 に答える
0
これは私のJavaScriptへの貢献です（再帰なし）
set = ["q0", "q1", "q2", "q3"]
collector = []
function comb(num) {
results = []
one_comb = []
for (i = set.length - 1; i >= 0; --i) {
tmp = Math.pow(2, i)
quotient = parseInt(num / tmp)
results.push(quotient)
num = num % tmp
}
k = 0
for (i = 0; i < results.length; ++i)
if (results[i]) {
++k
one_comb.push(set[i])
}
if (collector[k] == undefined)
collector[k] = []
collector[k].push(one_comb)
}
sum = 0
for (i = 0; i < set.length; ++i)
sum += Math.pow(2, i)
for (ii = sum; ii > 0; --ii)
comb(ii)
cnt = 0
for (i = 1; i < collector.length; ++i) {
n = 0
for (j = 0; j < collector[i].length; ++j)
document.write(++cnt, " - " + (++n) + " - ", collector[i][j], "<br>")
document.write("<hr>")
}
于 2012-05-03T20:42:36.120 に答える
0
C# の単純なアルゴリズム。（皆さんがアップロードしたものを使用しようとしたので投稿していますが、何らかの理由でコンパイルできませんでした-クラスを拡張しますか？他の誰かが同じ問題に直面している場合に備えて、独自のものを書きましたやった）。ちなみに、私は基本的なプログラミングほどC#には興味がありませんが、これは問題なく動作します。
public static List<List<int>> GetSubsetsOfSizeK(List<int> lInputSet, int k)
{
List<List<int>> lSubsets = new List<List<int>>();
GetSubsetsOfSizeK_rec(lInputSet, k, 0, new List<int>(), lSubsets);
return lSubsets;
}
public static void GetSubsetsOfSizeK_rec(List<int> lInputSet, int k, int i, List<int> lCurrSet, List<List<int>> lSubsets)
{
if (lCurrSet.Count == k)
{
lSubsets.Add(lCurrSet);
return;
}
if (i >= lInputSet.Count)
return;
List<int> lWith = new List<int>(lCurrSet);
List<int> lWithout = new List<int>(lCurrSet);
lWith.Add(lInputSet[i++]);
GetSubsetsOfSizeK_rec(lInputSet, k, i, lWith, lSubsets);
GetSubsetsOfSizeK_rec(lInputSet, k, i, lWithout, lSubsets);
}
利用方法：GetSubsetsOfSizeK(set of type List<int>, integer k)
それを変更して、作業しているものを反復処理できます。
幸運を！
于 2015-01-19T19:38:26.520 に答える
0
Python では、再帰とすべてが参照によって行われるという事実を利用します。これは、非常に大きなセットの場合に多くのメモリを消費しますが、初期セットが複雑なオブジェクトになる可能性があるという利点があります。ユニークな組み合わせだけを見つけます。
import copy
def find_combinations( length, set, combinations = None, candidate = None ):
# recursive function to calculate all unique combinations of unique values
# from [set], given combinations of [length]. The result is populated
# into the 'combinations' list.
#
if combinations == None:
combinations = []
if candidate == None:
candidate = []
for item in set:
if item in candidate:
# this item already appears in the current combination somewhere.
# skip it
continue
attempt = copy.deepcopy(candidate)
attempt.append(item)
# sorting the subset is what gives us completely unique combinations,
# so that [1, 2, 3] and [1, 3, 2] will be treated as equals
attempt.sort()
if len(attempt) < length:
# the current attempt at finding a new combination is still too
# short, so add another item to the end of the set
# yay recursion!
find_combinations( length, set, combinations, attempt )
else:
# the current combination attempt is the right length. If it
# already appears in the list of found combinations then we'll
# skip it.
if attempt in combinations:
continue
else:
# otherwise, we append it to the list of found combinations
# and move on.
combinations.append(attempt)
continue
return len(combinations)
このように使用します。「結果」を渡すことはオプションなので、それを使用して可能な組み合わせの数を取得できます...ただし、それは非常に非効率的です（計算で行う方がよいでしょう）。
size = 3
set = [1, 2, 3, 4, 5]
result = []
num = find_combinations( size, set, result )
print "size %d results in %d sets" % (size, num)
print "result: %s" % (result,)
そのテスト データから次の出力が得られるはずです。
size 3 results in 10 sets
result: [[1, 2, 3], [1, 2, 4], [1, 2, 5], [1, 3, 4], [1, 3, 5], [1, 4, 5], [2, 3, 4], [2, 3, 5], [2, 4, 5], [3, 4, 5]]
セットが次のようになっている場合も同様に機能します。
set = [
[ 'vanilla', 'cupcake' ],
[ 'chocolate', 'pudding' ],
[ 'vanilla', 'pudding' ],
[ 'chocolate', 'cookie' ],
[ 'mint', 'cookie' ]
]
于 2011-12-24T16:34:58.143 に答える
0
これは、単純で理解できない再帰的な C++ ソリューションです。
#include<vector>
using namespace std;
template<typename T>
void ksubsets(const vector<T>& arr, unsigned left, unsigned idx,
vector<T>& lst, vector<vector<T>>& res)
{
if (left < 1) {
res.push_back(lst);
return;
}
for (unsigned i = idx; i < arr.size(); i++) {
lst.push_back(arr[i]);
ksubsets(arr, left - 1, i + 1, lst, res);
lst.pop_back();
}
}
int main()
{
vector<int> arr = { 1, 2, 3, 4, 5 };
unsigned left = 3;
vector<int> lst;
vector<vector<int>> res;
ksubsets<int>(arr, left, 0, lst, res);
// now res has all the combinations
}
于 2020-12-12T10:21:51.297 に答える
-1
#include <unistd.h>
#include <stdio.h>
#include <iconv.h>
#include <string.h>
#include <errno.h>
#include <stdlib.h>
int main(int argc, char **argv)
{
int opt = -1, min_len = 0, max_len = 0;
char ofile[256], fchar[2], tchar[2];
ofile[0] = 0;
fchar[0] = 0;
tchar[0] = 0;
while((opt = getopt(argc, argv, "o:f:t:l:L:")) != -1)
{
switch(opt)
{
case 'o':
strncpy(ofile, optarg, 255);
break;
case 'f':
strncpy(fchar, optarg, 1);
break;
case 't':
strncpy(tchar, optarg, 1);
break;
case 'l':
min_len = atoi(optarg);
break;
case 'L':
max_len = atoi(optarg);
break;
default:
printf("usage: %s -oftlL\n\t-o output file\n\t-f from char\n\t-t to char\n\t-l min seq len\n\t-L max seq len", argv[0]);
}
}
if(max_len < 1)
{
printf("error, length must be more than 0\n");
return 1;
}
if(min_len > max_len)
{
printf("error, max length must be greater or equal min_length\n");
return 1;
}
if((int)fchar[0] > (int)tchar[0])
{
printf("error, invalid range specified\n");
return 1;
}
FILE *out = fopen(ofile, "w");
if(!out)
{
printf("failed to open input file with error: %s\n", strerror(errno));
return 1;
}
int cur_len = min_len;
while(cur_len <= max_len)
{
char buf[cur_len];
for(int i = 0; i < cur_len; i++)
buf[i] = fchar[0];
fwrite(buf, cur_len, 1, out);
fwrite("\n", 1, 1, out);
while(buf[0] != (tchar[0]+1))
{
while(buf[cur_len-1] < tchar[0])
{
(int)buf[cur_len-1]++;
fwrite(buf, cur_len, 1, out);
fwrite("\n", 1, 1, out);
}
if(cur_len < 2)
break;
if(buf[0] == tchar[0])
{
bool stop = true;
for(int i = 1; i < cur_len; i++)
{
if(buf[i] != tchar[0])
{
stop = false;
break;
}
}
if(stop)
break;
}
int u = cur_len-2;
for(; u>=0 && buf[u] >= tchar[0]; u--)
;
(int)buf[u]++;
for(int i = u+1; i < cur_len; i++)
buf[i] = fchar[0];
fwrite(buf, cur_len, 1, out);
fwrite("\n", 1, 1, out);
}
cur_len++;
}
fclose(out);
return 0;
}
ここで私のC ++での実装は、すべての組み合わせを指定されたファイルに書き込みますが、動作は変更できます。さまざまな辞書を生成するために作成しました。最小および最大の長さと文字範囲を受け入れます。現在サポートされているのはansiのみです。私のニーズには十分です
于 2012-09-16T12:53:19.387 に答える