すべての異なる組み合わせを返す有効なアルゴリズムはありますか？

Question

EDITED：私は組み合わせを意味していない順列

は、指定された配列から全て異なる順列を返します実効アルゴリズムはありますか？ A、B、C、D、E、F、G、H、I、J、K、...]

例：AB、AC、AD、..、DE、..、HI、..、ABC、ABD、...、DEF、..、CDEFG、...、ABCDEFGHIJK、....

いくつかのアルゴリズムが見つかりましたが、すべての並べ替えが返されますが、異なるものは返されません。

1. AB & BAは同じ順列

2. あるDEF & FED & EFD & DFEは

Answer 1

私が考えることができる最高のバイナリカウンタの一種である：ここで

A B C 
------- 
0 0 0 | Empty Set 
0 0 1 | C 
0 1 0 | B 
0 1 1 | BC 
1 0 0 | A 
1 0 1 | AC 
1 1 0 | AB 
1 1 1 | ABC 

Answer 2

1. として、同じ順列です：異なることで私がいることを意味しますコメントによって指摘されている、あなたはすべてを列挙することを目指しているサブセットであり、順列ではない。

2. これを行う最も簡単な方法は、バイナリカウンタを使用することです。

コード：：私はこれが

Answer 3

あなたの質問に答えるのに役立ちます願ってい

for(int i=0; i<(1<<n); ++i) { 
    //Bits of i represent subset, eg. element k is contained in subset if i&(1<<k) is set. 
} 

これらのではない順列たとえば、あなたは、このような何かがCに働くだろう、n型の要素を持っていると仮定。 の順列はABCです。{ABC, ACB, BCA, BAC, CAB, CBA}です。 のすべての異なるサブセット（別名、power set）が{A,B,C, ..., K, ...}であることがわかります。これは簡単です：各要素は含まれているか除外されています。ここでは、再帰的なアルゴリズムです：

power_set(U) = 
    if U == {} then 
     {{}};  
    else 
     union({ first(U), power_set(tail(U)) }, // include 
      { power_set(tail(U)) }    // exclude 
      ); 

Answer 4

どれ与えられたアイテムを組み合わせてかないのいずれかです。それぞれの項目にブール値のフラグを付けて、それがコンビネーションに含まれているかどうかを判断します。ブール値フラグの可能なすべてのリストを調べると、すべての組み合わせが完了しています。

ブール値のリストは、バイナリ整数とも呼ばれます。

アイテムA-Kがある場合は、11個のアイテムがあります。だから、すべての可能な11ビット番号を調べてください。 Javaの場合：

for (int flags = 0; flags < (1 << 11); ++flags) { 
    int x = indexOfSomeItemFromZeroToTen(); 
    boolean isInCombination = ((i >> x) & 1) == 1; 
} 

空の組み合わせをスキップする場合は、0ではなく1から開始します。

Answer 5

は、私は今、アレイ内の各組み合わせを反復処理し、そのしばらくのために書かれたと持っていたいくつかのRubyコードです。

def _pbNextComb(comb,length) # :nodoc: 
i=comb.length-1 
begin 
    valid=true 
    for j in i...comb.length 
    if j==i 
    comb[j]+=1 
    else 
    comb[j]=comb[i]+(j-i) 
    end 
    if comb[j]>=length 
    valid=false 
    break 
    end 
    end 
    return true if valid 
    i-=1 
end while i>=0 
return false 
end 

# 
# Iterates through the array and yields each 
# combination of _num_ elements in the array 
# 
# Takes an array and the number of elemens 
# in each combination 
def pbEachCombination(array,num) 
return if array.length<num || num<=0 
if array.length==num 
    yield array 
    return 
elsif num==1 
    for x in array 
    yield [x] 
    end 
    return 
end 
currentComb=[] 
arr=[] 
for i in 0...num 
    currentComb[i]=i 
end 
begin 
    for i in 0...num 
    arr[i]=array[currentComb[i]] 
    end 
    yield arr 
end while _pbNextComb(currentComb,array.length) 
end