1

これを行う方法をインターネットでたくさん検索しましたが、完全に理解できるものは思いつきませんでした。

各グループの文字数を指定して、文字の配列から可能なすべての組み合わせを生成しようとしています。次に例を示します。

手紙:A, B, C

長さ:2

結果:AB, AC, BC

(次のようなものがあることはわかっていますがBA、グループCACB取得するだけで、順序は関係ありません。)

例2:

手紙:A, B, C, D

長さ:3

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

など…</p>

そのアルゴリズムをC++で実装するつもりですが、C#、Java、またはJavascriptの例も歓迎します。

4

4 に答える 4

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
于 2012-04-12T15:53:08.243 に答える
1

再帰に適しているようです。各要素を取得し、指定された深さが満たされるまで残りの組み合わせに追加します。

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;
}
于 2012-04-12T15:52:08.933 に答える
1

これは順列として知られており、解決策はたくさんあります。これは私が書いた非再帰的なもので、超高速です。(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
于 2015-12-14T16:40:28.313 に答える
0

これは、少し調整すれば機能するはずです。

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:53:23.957 に答える