3

リストのすべての事前定義された長さの順列を昇順で取得しようとしています。 

For example, take the set:  "ABCDE"
I'd like the returning result to be:
ABC, ABD, ABE, ACD, ACE, ADE, BCD, BCE, BDE, CDE

つまり、「B」が「A」の前に現れることはありません (昇順) が、この要件内のすべてのバリエーションが必要です。

私は LINQ を使用したくないので、これを実装する最速の方法を見つけようとしています (このアプリでは速度が重要です)。

これまでのところ、文字のリストのリストがあります:

List<List<char>> Combinations;

ここで、内側の「リスト」は「ABC」のような組み合わせ (各文字は文字) であり、外側のリストはすべての組み合わせのリストになります。

結果の各セット (上記の例では 3) の長さは動的である必要があるため、何らかの再帰が必要になると考えています...実装方法がわかりません。

どんな助けでも大歓迎です！

編集

これまでのところ、これが私が持っているものです（私は近づいているように感じます...実際に最終リストを作成することはできません（ユニオンが機能していません-間違って使用していますか？）：

    private List<List<char>> AscendingPermute(List<char> InMovements, int Combinations)
    {
        List<List<char>> Ret = new List<List<char>>();

        for(int i = 0; i <= InMovements.Count - Combinations; i++)
        {
            if(Combinations <= 1){
                Ret.Add(new List<char>() {InMovements[i] });
                return Ret;
            }
            else
            {
                Ret.Union(AscendingPermute(InMovements.GetRange(1, InMovements.Count - 1), Combinations - 1));
            }
        }

        return Ret;
    }

私は正しい軌道に乗っていますか？私は何が欠けていますか？

ありがとう！

4

5 に答える 5

5

n 個の要素のセットから可能なすべての k 要素が必要であり、各 k 要素を昇順でリストする必要がありますか?

ここを見てください: n から k 個の要素のすべての組み合わせを返すアルゴリズム

于 2012-04-04T20:16:54.900 に答える
3

私は速度について肯定的ではありませんが、これはあなたが探しているものだと思います:

public static IEnumerable<string> GetPermutations(string letters, int max = 3, int curr = 0)
{
  if (curr < max - 1)
  {
    for (int a = 0; a < letters.Length; a++)
    {
      string firstHalf = letters.Substring(a,1);
      string subset = letters.Substring(a+1);
      foreach (string secondHalf in GetPermutations(subset, max, curr + 1))
      {
        //Console.Write("1st: {0}, 2nd: {1}; set: {2}", firstHalf, secondHalf, subset);
        yield return firstHalf + secondHalf;
      }
    }
  }
  else
    yield return String.Empty;
}

呼び出しの例:

foreach (var result in GetPermutations('ABCDE', 3)){
  Console.WriteLine(result);
}

結果:

ABC
ABD
ABE
ACD
ACE
ADE
BCD
BCE
BDE
CDE
Press any key to continue...
于 2012-04-04T20:50:00.370 に答える
2

再帰は必要ありません。 

List<string> sortedResult = Perm("ABCDE",3);

static int BitCount(int n)
{
    int test = n,count = 0;

    while (test != 0)
    {
        if ((test & 1) == 1) count++;
        test >>= 1;
    }
    return count;
}


static List<string> Perm(string input,int M)
{
    var chars = input.ToCharArray();
    int N = chars.Length;
    List<List<char>> result = new List<List<char>>();

    for (int i = 0; i < Math.Pow(2, N); i++)
    {
        if (BitCount(i) == M)
        {
            List<char> line = new List<char>();
            for (int j = 0; j < N; j++)
            {
                if (((i >> j) & 1) == 1)
                {
                    line.Add(chars[j]);
                }
            }
            result.Add(line);
        }
    }

    return result.Select(l => String.Join("", l)).OrderBy(s => s).ToList();
}
于 2012-04-04T20:51:27.107 に答える
0

次を計算する再帰関数を探しています: 指定されたアルファベットの最初の文字 (昇順でソート) を、アルファベットの残りの文字を 1 文字減らした昇順の順列と、同じ文字を含む残りの昇順の順列を連結したものカウント。

明確にするために、あなたの例では

asc_perm("ABCDE",3):="A"+asc_perm("BCDE",2) | asc_perm("BCDE",3)

反復的にコーディングするには、およびnという制約を使用してアルファベットにインデックスを設定し、可能なすべてのインデックスを列挙します。これは、いくつかの追加条件を備えた一種のカウンターです。これらのインデックスを使用してカウントするには、 から始めます。アルファベットの長さに達するまで、最後のカウンターをインクリメントすることから始めます。その場合は、前のインデックスを見つけて 1 ずつ増やし、インデックスがカウントより大きくならない限り、それに続くすべてのインデックスを に設定します。存在する場合は、有効な位置がなくなるまで、前のインデックスでプロセスを繰り返します。n>m => idx_{n} > idx_{m}0 < n,m <= count(alphabet)1, 2, 3, 4, ...n1+idx_prev

例の簡単な概要は次のとおりです。

  • 初期状態：{1,2,3}
  • すべての有効な位置の最後のインデックスを実行します: {1,2,4},{1,2,5}
  • 前のインデックス (2) を次にインクリメントし、残りをリセットします。{1,3,4}
  • すべての有効な位置に対して最後のインデックスを実行します。{1,3,5}
  • 前のインデックス (2) を次にインクリメントし、残りをリセットします。{1,4,5}
  • すべての有効な位置の最後のインデックスを実行します: 可能な動きはありません
  • 前のインデックス (2) を次のインデックスにインクリメントし、残りをリセットします: 可能な移動はありません
  • 前のインデックス (1) を次にインクリメントし、残りをリセットします。{2,3,4}
  • すべての有効な位置に対して最後のインデックスを実行します。{2,3,5}
  • 前のインデックス (2) を次にインクリメントし、残りをリセットします。{2,4,5}
  • すべての有効な位置の最後のインデックスを実行します: 可能な動きはありません
  • 前のインデックス (2) を次のインデックスにインクリメントし、残りをリセットします: 可能な移動はありません
  • 前のインデックス (1) を次にインクリメントし、残りをリセットします。{3,4,5}
  • すべての有効な位置の最後のインデックスを実行します: 可能な動きはありません
  • 前のインデックス (2) を次のインデックスにインクリメントし、残りをリセットします: 可能な移動はありません
  • 前のインデックス (1) を次のインデックスにインクリメントし、残りをリセットします: 可能な移動はありません
  • 終了
于 2012-04-04T20:24:26.387 に答える
0

これは、あなたが望むことをする再帰的な方法です:

    static IEnumerable<List<byte>> AscPerm(List<byte> inBytes, int combinations)
    {
        if (combinations == 1)
        {
            foreach (var b in inBytes)
            {
                yield return new List<byte> { b };
            }
        }
        else
        {
            for (int i = 0; i <= inBytes.Count - combinations; i++)
            {
                // Recurse down, passing last items of inBytes.
                var subPerms = AscPerm(inBytes.Skip(i +1).ToList(), combinations - 1);
                foreach (var subPerm in subPerms)
                {
                    List<byte> retBytes = new List<byte>{ inBytes[i] };
                    yield return retBytes.Concat(subPerm).ToList();
                }
            }
        }
    }

    static void Main(string[] args)
    {
        var retList = AscPerm(new List<byte> { 1, 2, 3, 4, 5, 6, 7 }, 3);
        foreach (var ret in retList)
        {
            foreach (var r in ret)
            {
                Console.Write(r);
            }
            Console.WriteLine();
        }
        Console.ReadLine();
    }
于 2012-04-04T21:38:54.703 に答える