我要在列表中加载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个过程,该如何做?我曾想过一会儿..do循环一个用于计数器,一个用于组计数,但是这有点困难,我想知道是否有一些更简单,快速的解决方案,也可以使用运算符boolean或类似的东西。谁能给我一些建议?非常感谢。
似乎您正在寻找一种快速算法来计算所有k个组合。以下Delphi代码是此处找到的C代码的直接翻译:Generating Combinations。我什至修复了该代码中的错误!
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的集合,有一个lot子集。
输出不是您想要的顺序,但是如果对您而言很重要,那么可以很容易地进行补救。
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系统,因此我将其清理并添加了警告消息,用法和能够在命令行上提供设置大小和子集大小。还梳[]有已转换为更通用的整数数组指针,并使用了calloc将可能需要的任何设置大小的内存清零。
除非您不能根据某些要求进行函数调用,否则请执行以下操作:
跟随David发布的链接,然后单击浏览,使我找到了一篇文章,他们用术语“银行家的搜索”创造了这个词,这似乎很适合您的模式。
我在这里创建了此脚本,并且效果很好:
这里真的很愚蠢:您可以从0到X进行计数(x是二进制的1111 .... 1填充到要选择的内容列表中),并且拒绝该计数的所有没有字符串的二进制值计数“ 1”等于您要选择的数量?