文字群からの単語の組み合わせを取得する

Question

私はこれを行う方法をインターネットでたくさん探しましたが、私は完全に理解しているものを考え出しませんでした。

文字：例えば、各グループ内の文字の量を指定することにより、文字の配列からのすべての可能な組み合わせを生成しようと

イムA, B, C

長さ：2

結果： AB, AC, BC

（私には：BA,CAおよびCBもありますが順序は問題ではないグループ）

例2：

手紙：A, B, C, D

長さ：3

結果：ABC, ACD, BCD, CDA, DAB

と等...

IそのアルゴリズムをC++で実装しようとしますが、C＃、Java、Javascriptの例はwelcですオームも同様です。

Answer 1

あなたが再現可能な方法でそれらを注文する場合は、あなたがより簡単にそれらを生成するアルゴリズムを見つける：

5の3を取る、のは、それはあまりにも簡単ではないにしてみましょう：

e d c b a 
--------- 
    x x x abc 
    x x x abd 
x  x x abe 
    x x x acd 
x x x ace 
x x  x ade 
    x x x bcd 
x x x bce 
x x x bde 
x x x  cde 

Answer 2

再帰に適しているようです。与えられた深さが満たされるまで、各要素を取り、それを残りの組み合わせの先頭に付けます。

static List<String> func(List<String> a, Int32 depth) 
{ 
    List<String> retVal = new List<String>(); 
    if (depth <= 0) 
    { 
     return retVal; 
    } 
    for (int i = 0; i < a.Count; i++) 
    { 
     String element = a[i]; 

     List<String> temp = new List<String>(a); 
     temp.RemoveAt(i); 
     List<String> resultset = func(temp, depth - 1); 
     if (resultset.Count == 0) 
     { 
      retVal.Add(element); 
     } 
     else 
     { 

      foreach (String result in resultset) 
      { 
       retVal.Add(element + result); 
      } 
     } 
    } 
    return retVal; 
} 

Answer 3

あなたはそれを少し微調整した場合、この作業をする必要があります：

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); 
} 

説明hereを。

Answer 4

これは順列として知られていますが、そこには多くの解決策があります。 ここでは、私が書いた非再帰的なものがありますが、それは超高速です。 （Windowsの場合は、__builtin_ctzを使用する代わりに_BitScanReverseを参照する必要があります）。

#include <iostream> 
#include <cstdlib> 
using namespace std; 

void perm(unsigned &v) { //v must be initialised with t = (2 << N) - 1; 
    unsigned t = v | (v - 1); 
    v = (t + 1) | (((~t & -~t) - 1) >> (__builtin_ctz(v) + 1)); 
} 

int main (int argc, char *argv[]) { 
    unsigned n = argc > 1 ? atoi(argv[1]) : 3; //bins: 0..31 
    unsigned k = argc > 2 ? atoi(argv[2]) : 2; //things: 0 .. bins. 
    unsigned m = (1 << n) - 1; //bitmask is size of n (bins). 
    unsigned v = (1 << k) - 1; //start value - initial allocation. 
    do { 
     cout << bitset<31>(v & m) << endl; 
     perm(v); 
    } while (v < m); 
    return 0; 
} 

あなたの質問では、文字A、B、Cの長さ2を例としてお勧めします。 （私がコメントしている） ので、このコードは（引数として3 2を渡して）生成する

ABC 
011 //BC 
101 //AC 
110 //AB