使用せずにn要素を繰り返すことのない組み合わせ..to..do
https://stackoverflow.com/questions/8316479
-
25-10-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian質問
繰り返しのないn番号の組み合わせをリストにロードし、要素とグループを入力するために与えたいと思います。たとえば、4つの要素[1,2,3,4]で、私は以下を持っています。
Group 1: [1][2][3][4];
Group 2: [1,2][1,3][1,4][2,3][2,4][3,4];
Group 3: [1,2,3][1,2,4][1,3,4][2,3,4]
Group 4: [1,2,3,4]
今、私はネストされたループを使用してそれを解決しました。たとえば、グループ2で、私は次のように書きます。
for x1 := 1 to 3 do
for x2 := Succ(x1) to 4 do
begin
// x1, x2 //
end
またはグループ3については、次のように書いています。
for x1 := 1 to 2 do
for x2 := Succ(x1) to 3 do
for x3 := Succ(x2) to 4 do
begin
// x1, x2, x3 //
end
そして他のグループのために。一般に、グループNのためにそれをやりたい場合、できる限り、ネストされたループを使用してN手順を書き込むことなく？私はダブルを考えていますが、カウンターに使用するために1つ、グループカウントに使用するために使用することはありませんが、少し難しいです。オペレーターブールまたは何かを使用して、よりシンプルで高速なソリューションがあるかどうかを知りたかったのです。 。誰が私にそれについて提案することができますか？どうもありがとう。
解決
すべてのK-buminationを計算するための高速アルゴリズムを探しているようです。次のDelphiコードは、ここにあるCコードの直接翻訳です。 組み合わせの生成. 。そのコードのバグも修正しました！
program kCombinations;
{$APPTYPE CONSOLE}
// Prints out a combination like {1, 2}
procedure printc(const comb: array of Integer; k: Integer);
var
i: Integer;
begin
Write('{');
for i := 0 to k-1 do
begin
Write(comb[i]+1);
if i<k-1 then
Write(',');
end;
Writeln('}');
end;
(*
Generates the next combination of n elements as k after comb
comb => the previous combination ( use (0, 1, 2, ..., k) for first)
k => the size of the subsets to generate
n => the size of the original set
Returns: True if a valid combination was found, False otherwise
*)
function next_comb(var comb: array of Integer; k, n: Integer): Boolean;
var
i: Integer;
begin
i := k - 1;
inc(comb[i]);
while (i>0) and (comb[i]>=n-k+1+i) do
begin
dec(i);
inc(comb[i]);
end;
if comb[0]>n-k then// Combination (n-k, n-k+1, ..., n) reached
begin
// No more combinations can be generated
Result := False;
exit;
end;
// comb now looks like (..., x, n, n, n, ..., n).
// Turn it into (..., x, x + 1, x + 2, ...)
for i := i+1 to k-1 do
comb[i] := comb[i-1]+1;
Result := True;
end;
procedure Main;
const
n = 4;// The size of the set; for {1, 2, 3, 4} it's 4
k = 2;// The size of the subsets; for {1, 2}, {1, 3}, ... it's 2
var
i: Integer;
comb: array of Integer;
begin
SetLength(comb, k);// comb[i] is the index of the i-th element in the combination
//Setup comb for the initial combination
for i := 0 to k-1 do
comb[i] := i;
// Print the first combination
printc(comb, k);
// Generate and print all the other combinations
while next_comb(comb, k, n) do
printc(comb, k);
end;
begin
Main;
Readln;
end.
出力
{1,2}
{1,3}
{1,4}
{2,3}
{2,4}
{3,4}
他のヒント
これがビットセットに依存しているかなり楽しいソリューションです。現状では、32以下のサイズのセットに限定されています。 多く 32を超えるカーディナリティのセットのサブセットの。
出力はあなたが望む順序ではありませんが、それがあなたにとって重要な場合、それは簡単に改善するのに十分簡単です。
program VisitAllSubsetsDemo;
{$APPTYPE CONSOLE}
procedure PrintBitset(Bitset: Cardinal; Size: Integer);
var
i: Integer;
Mask: Cardinal;
SepNeeded: Boolean;
begin
SepNeeded := False;
Write('{');
for i := 1 to Size do begin
Mask := 1 shl (i-1);
if Bitset and Mask<>0 then begin
if SepNeeded then begin
Write(',');
end;
Write(i);
SepNeeded := True;
end;
end;
Writeln('}');
end;
procedure EnumerateSubsets(Size: Integer);
var
Bitset: Cardinal;
begin
for Bitset := 0 to (1 shl Size)-1 do begin
PrintBitset(Bitset, Size);
end;
end;
begin
EnumerateSubsets(4);
end.
出力
{}
{1}
{2}
{1,2}
{3}
{1,3}
{2,3}
{1,2,3}
{4}
{1,4}
{2,4}
{1,2,4}
{3,4}
{1,3,4}
{2,3,4}
{1,2,3,4}
そして、ここに、指定されたカーディナリティのサブセットをリストするだけのバリアントがあります。
function SetBitCount(Bitset: Cardinal; Size: Integer): Integer;
var
i: Integer;
Mask: Cardinal;
begin
Result := 0;
for i := 1 to Size do begin
Mask := 1 shl (i-1);
if Bitset and Mask<>0 then begin
inc(Result);
end;
end;
end;
procedure EnumerateSubsets(Size, NumberOfSetBits: Integer);
var
Bitset: Cardinal;
begin
for Bitset := 0 to (1 shl Size)-1 do begin
if SetBitCount(Bitset, Size)=NumberOfSetBits then begin
PrintBitset(Bitset, Size);
end;
end;
end;
begin
EnumerateSubsets(4, 2);
end.
出力
{1,2}
{1,3}
{2,3}
{1,4}
{2,4}
{3,4}
これは何度も繰り返される質問であるように思われ、数ビットのコードがその問題について蹴っています。一部のコードの非常に優れたアルゴリズムが記述されていますが、それは厳密にクリーンなCではなく、UNIXやLinux、またはPOSIXシステムにポータブルではないため、クリーンアップして、警告メッセージ、使用法、設定されたサイズと設定されたサイズを提供する機能を追加しました。コマンドラインのsub_setサイズ。また、Comb []は、より一般的なポインターに移行され、整数の配列とCallocが必要なサイズのサイズに必要なメモリをゼロにするために使用されます。
以下はISO IEC 9899：1999 C Clean：
/*********************************************************************
* The Open Group Base Specifications Issue 6
* IEEE Std 1003.1, 2004 Edition
*
* An XSI-conforming application should ensure that the feature
* test macro _XOPEN_SOURCE is defined with the value 600 before
* inclusion of any header. This is needed to enable the
* functionality described in The _POSIX_C_SOURCE Feature Test
* Macro and in addition to enable the XSI extension.
*
* Compile with c99 or with gcc and CFLAGS to include options
* -std=iso9899:199409 -pedantic-errors in order to ensure compliance
* with ISO IEC 9899:1999 C spec.
*
* Code cleanup and transition to comb as a pointer to type ( int * )
* array by Dennis Clarke dclarke@blastwave.org 28 Dec 2012
*
*********************************************************************/
#define _XOPEN_SOURCE 600
#include <stdio.h>
#include <stdlib.h>
/* Prints out a combination like {1, 2} */
void printc( int *comb, int k) {
int j;
printf("{ ");
for ( j = 0; j < k; ++j )
printf("%d , ", *( comb + j ) + 1 );
printf( "\b\b}\n" );
} /* printc */
/**********************************************************************
next_comb(int comb[], int k, int n)
Generates the next combination of n elements as k after comb
comb => the previous combination ( use (0, 1, 2, ..., k) for first)
k => the size of the subsets to generate
n => the size of the original set
Returns: 1 if a valid combination was found
0, otherwise
**********************************************************************/
int next_comb( int *comb, int k, int n) {
int i = k - 1;
++*( comb + i );
while ( ( i >= 0 ) && ( *( comb + i ) >= n - k + 1 + i ) ) {
--i;
++*( comb + i );
}
if ( *comb > n - k) /* Combination (n-k, n-k+1, ..., n) reached */
return 0; /* No more combinations can be generated */
/* comb now looks like (..., x, n, n, n, ..., n).
* Turn it into (..., x, x + 1, x + 2, ...) */
for (i = i + 1; i < k; ++i)
*( comb + i ) = *( comb + ( i - 1 ) ) + 1;
return 1;
} /* next_comb */
int main(int argc, char *argv[]) {
int *comb, i, n, k;
n = 9; /* The size of the set; for {1, 2, 3, 4} it's 4 */
k = 6; /* The size of the subsets; for {1, 2}, {1, 3}, .. it's 2 */
if ( argc < 3 ) {
printf ( "\nUSAGE : %s n k\n", argv[0] );
printf ( " : Where n is the set size and k the sub set size.\n" );
printf ( " : Note that k <= n\n" );
return ( EXIT_FAILURE );
}
n = atoi ( argv[1] );
k = atoi ( argv[2] );
if ( k > n ) {
printf ( "\nWARN : k > n is not allowed.\n" );
printf ( "USAGE : %s n k\n", argv[0] );
printf ( " : Where n is the set size and k the sub set size.\n" );
printf ( " : Note that k <= n\n" );
return ( EXIT_FAILURE );
}
comb = ( int * ) calloc( (size_t) k, sizeof(int) );
for ( i = 0; i < k; ++i)
*( comb + i ) = i;
/* Print the first combination */
printc( comb, k );
/* Generate and print all the other combinations */
while ( next_comb( comb, k, n ) )
printc( comb, k );
free ( comb );
return ( EXIT_SUCCESS );
}
したがって、上記をOpteronベースのマシンにコンパイルすることができます。
$ echo $CFLAGS
-m64 -g -malign-double -std=iso9899:199409 -pedantic-errors -mno-mmx
-mno-sse -fexceptions -fpic -fvisibility=default -mtune=opteron
-march=opteron -m128bit-long-double -mpc80 -Wl,-q
$ gcc $CFLAGS -o combinations combinations.c
したがって、10のセットサイズとサブセット6のセットサイズの簡単な些細なテストは次のとおりです。
$ ./combinations 10 6 | wc -l
210
数学は正しい：
( 10 ! ) / ( ( 10 - 6 )! * ( 6! ) ) = 210 unique combinations.
整数アレイコームがポインターシステムに基づいているため、利用可能なメモリと時間によってのみ制限されます。したがって、次のことがあります。
$ /usr/bin/time -p ./combinations 20 6 | wc -l
real 0.11
user 0.10
sys 0.00
38760
これは正しいように見えます：
( 20 ! ) / ( ( 20 - 6 )! * ( 6! ) ) = 38,760 unique combinations
このように、私たちは今、制限を少し押し上げるかもしれません：
$ ./combinations 30 24 | wc -l
593775
繰り返しますが、数学は結果に同意します。
( 30 ! ) / ( ( 30 - 24 )! * ( 24! ) ) = 593 775 unique combinations
システムの限界を自由に押してください：
$ /usr/bin/time -p ./combinations 30 22 | wc -l
real 18.62
user 17.76
sys 0.83
5852925
私はまだもっと大きなことを試していませんが、数学はこれまでの出力と同様に正しいように見えます。修正が必要な場合はお気軽にお知らせください。
Dennis Clarke dclarke@blastwave.org 2012年12月28日
いくつかの要件で関数呼び出しを行うことができない限り、これを行います。
select_n_from_list(int *selected, int n, int *list, int list_size):
if (n==0) {
// print all numbers from selected by traversing backward
// you can set the head to a special value or make the head location
// a static variable for lookup
}
for (int i=0; i<=list_size-n; i++) {
*selected = list[i];
select_n_from_list(selected+1, n-1, list+i+1, list_size-i-1);
}
}
中間結果には自動ストレージが必要なため、何らかの再帰が必要です。このソリューションが機能しないようにする特別な要件があるかどうかを教えてください。
Davidが投稿してクリックしたリンクに従って、私はあなたのパターンに合っているように見える「Banker's Search」という用語を生み出す記事に私を導きました。
この記事は、C ++の例のソリューションを提供し、再帰を利用してください。
ここでこのスクリプトを作成し、非常にうまく機能しました。
$(document).ready(function(){
$("#search").on('click', function(){
var value = $("#fieldArray").val().split(",");
var results = new SearchCombinations(value);
var output = "";
for(var $i = 0; $i< results.length;$i++){
results[$i] = results[$i].join(",");
output +="<li>"+results[$i]+"</li>";
}
$("#list").html(output);
});
});
/*Helper Clone*/
var Clone = function (data) {
return JSON.parse(JSON.stringify(data));
}
/*Script of Search All Combinations without repetitions. Ex: [1,2,3]*/
var SearchCombinations = function (statesArray) {
var combinations = new Array(),
newValue = null,
arrayBeforeLevel = new Array(),
$level = 0,
array = new Clone(statesArray),
firstInteration = true,
indexFirstInteration = 0,
sizeValues = array.length,
totalSizeValues = Math.pow(2, array.length) - 1;
array.sort();
combinations = new Clone(array);
arrayBeforeLevel = new Clone(array);
loopLevel: while ($level < arrayBeforeLevel.length) {
for (var $i = 0; $i < array.length; $i++) {
newValue = arrayBeforeLevel[$level] + "," + array[$i];
newValue = newValue.split(",");
newValue.sort();
newValue = newValue.join(",");
if (combinations.indexOf(newValue) == -1 && arrayBeforeLevel[$level].toString().indexOf(array[$i]) == -1) {
if (firstInteration) {
firstInteration = false;
indexFirstInteration = combinations.length
}
sizeValues++;
combinations.push(newValue);
if (sizeValues == totalSizeValues) {
break loopLevel;
}
}
}
$level++;
if ($level == arrayBeforeLevel.length) {
firstInteration = true;
arrayBeforeLevel = new Clone(combinations);
arrayBeforeLevel = arrayBeforeLevel.splice(indexFirstInteration);
indexFirstInteration = 0;
$level = 0;
}
}
for (var $i = 0; $i < combinations.length; $i++) {
combinations[$i] = combinations[$i].toString().split(",");
}
return combinations;
}*{font-family: Arial;font-size:14px;}
small{font-size:11px}<script src="https://ajax.googleapis.com/ajax/libs/jquery/1.11.1/jquery.min.js"></script>
<label for="">
<input type="text" id="fieldArray">
<button id="search">Search</button>
<br><small>Info the elements. Ex: "a,b,c"</small>
</label>
<hr>
<ul id="list"></ul>所属していません StackOverflow
