0

次の文字について、a,b,c,d次の組み合わせを見つけたいと思います。

シーケンスは常にソートされます。組み合わせを見つけるにはどのようにアプローチすればよいのでしょうか。

a
b
c
d

ab
交流
広告

紀元前
BD

CD

abc
アブド
acd

bcd

あいうえお
4

5 に答える 5

4

あなたが望むのは、すべての組み合わせです。通常、組み合わせを取得すると、特定のサイズ n のすべての組み合わせが取得されます。シーケンスからサイズ n の組み合わせを取得するメソッドを作成することから始めます。

public static IEnumerable<IEnumerable<T>> Combinations<T>(
      this IEnumerable<T> source, int n)
{
    if (n == 0)
        yield return Enumerable.Empty<T>();


    int count = 1;
    foreach (T item in source)
    {
        foreach (var innerSequence in source.Skip(count).Combinations(n - 1))
        {
            yield return new T[] { item }.Concat(innerSequence);
        }
        count++;
    }
}

それができたら、1 からシーケンスのサイズまでのすべての n に対する n の組み合わせを取得するのは簡単なことです。

public static IEnumerable<IEnumerable<T>> AllCombinations<T>(this IList<T> source)
{
    IEnumerable<IEnumerable<T>> output = Enumerable.Empty<IEnumerable<T>>();
    for (int i = 0; i < source.Count; i++)
    {
        output = output.Concat(source.Combinations(i));
    }
    return output;
}

それを使用するいくつかのサンプル コード:

var list = new List<string> { "a", "b", "c", "d" };

foreach (var sequence in list.AllCombinations())
{
    Console.WriteLine(string.Join(" ", sequence));
}

この操作は、最も小さな入力シーケンスを除いて、非常にコストがかかることに注意してください。これは正確には最も効率的ではありませんが、パフォーマンスの最後のビットをすべて探し出したとしても、待機する時間と時間によっては、15 ～ 20 を超えるシーケンスの組み合わせを計算することはできません。あなたのコンピュータがどれほど優れているか。

于 2012-10-22T15:28:32.957 に答える
0

二項係数を扱うための一般的な関数を処理するクラスを作成しました。これは、問題が該当するタイプの問題です。@Bobson によって提案された Cominatorics ライブラリは見ていませんが、私のクラスはおそらくはるかに高速で効率的だと思います。次のタスクを実行します。

  1. 任意の N choose K について、すべての K-index を適切な形式でファイルに出力します。K インデックスは、よりわかりやすい文字列または文字で置き換えることができます。

  2. K インデックスを、並べ替えられた二項係数テーブル内のエントリの適切なインデックスに変換します。この手法は、反復に依存する以前に公開された手法よりもはるかに高速です。これは、パスカルの三角形に固有の数学的性質を使用して行われます。私の論文はこれについて語っています。この手法を発見して公開したのは私が最初だと思いますが、間違っている可能性があります。

  3. ソートされた二項係数テーブルのインデックスを対応する K インデックスに変換します。あなたが見つけたリンクよりも速いかもしれないと思います。

  4. Mark Dominusメソッドを使用して二項係数を計算します。これは、オーバーフローする可能性がはるかに低く、より大きな数で機能します。

  5. このクラスは .NET C# で記述されており、問題に関連するオブジェクト (存在する場合) をジェネリック リストを使用して管理する方法を提供します。このクラスのコンストラクターは、InitTable と呼ばれる bool 値を受け取ります。これが true の場合、管理対象のオブジェクトを保持する汎用リストが作成されます。この値が false の場合、テーブルは作成されません。上記の 4 つの方法を実行するためにテーブルを作成する必要はありません。テーブルにアクセスするためのアクセサ メソッドが用意されています。

  6. クラスとそのメソッドの使用方法を示す関連するテスト クラスがあります。2 つのケースで広範囲にテストされており、既知のバグはありません。

このクラスについて読んでコードをダウンロードするには、二項係数の表化を参照してください。

問題の解決策には、N choose K ケースごとに K インデックスを生成することが含まれます。したがって、N (A、B、C、D) に 4 つの可能性がある上記の例では、(C# の) コードは次のようになります。

int TotalNumberOfValuesInSet = 4;
int N = TotalNumberOfValuesInSet;
// Loop thru all the possible groups of combinations.
for (int K = N - 1; K < N; K++)
{
   // Create the bin coeff object required to get all
   // the combos for this N choose K combination.
   BinCoeff<int> BC = new BinCoeff<int>(N, K, false);
   int NumCombos = BinCoeff<int>.GetBinCoeff(N, K);
   int[] KIndexes = new int[K];
   // Loop thru all the combinations for this N choose K case.
   for (int Combo = 0; Combo < NumCombos; Combo++)
   {
      // Get the k-indexes for this combination, which in this case
      // are the indexes to each letter in the set starting with index zero.
      BC.GetKIndexes(Loop, KIndexes);
      // Do whatever processing that needs to be done with the indicies in KIndexes.
      ...
   }
   // Handle the final combination which in this case is ABCD since since K < N.
   ...
}
于 2012-10-22T16:19:30.493 に答える
0

入力シーケンスに重複が含まれないようにするものがないため、これらは真のサブセットではありませんが、次の拡張メソッドは一般的なケースで機能するはずです。

public static IEnumerable<IEnumerable<T>> Subsets<T>(this IEnumerable<T> source)
{
    List<T[]> yielded = new List<T[]> { new T[0] };
    foreach(T t in source)
    {
        List<T[]> newlyYielded = new List<T[]>();
        foreach(var y in yielded)
        {
            var newSubset = y.Concat(new[] {t}).ToArray();
            newlyYielded.Add(newSubset);
            yield return newSubset;
        }
        yielded.AddRange(newlyYielded);
    }
}

基本的に空のシーケンスから始めて、最初の項目が追加された空のシーケンスを追加します。次に、これら 2 つのシーケンスのそれぞれについて、次の項目を追加してそのシーケンスを追加します。次に、これら 4 つのシーケンスのそれぞれについて...

これは、生成された各シーケンスのコピーを保持する必要があるため、大量のメモリを使用します。

文字列から文字列を取得するには、これを次のように呼び出すことができます

"abcd".Subsets().Select(chars => new string(chars.ToArray()))

多くの文字を持たない場合は、n 番目のサブセットを直接計算できるという事実を利用できます。

public static int SubsetCount(this string s)
{
    return 2 << s.Length;
}
public static string NthSubset(this string s, int n)
{
    var b = New StringBuilder();
    int i = 0;
    while (n > 0)
    {
        if ((n&1)==1) b.Append(s[i]);
        i++;
        n >>= 1;
    }
    return b.ToString();
}
于 2012-10-22T16:01:45.417 に答える
0

Combinatoricsライブラリを使用してそれらを計算できます (ドキュメント) が、Servy が言ったように、データの長さが所要時間の主な要因です。

于 2012-10-22T15:39:10.207 に答える