昇順リスト順列

Question

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

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）は動的である必要があるので、何らかの再帰が必要になると思っています...実装方法を理解できません。

ご協力いただければ幸いです！

EDIT

これまでのところ、ここで私は（私が近づいてるように感じる持っているものだ...私はちょうどそれが実際に最終的なリストを構築するために取得することはできません（労働組合が機能していません - 私が間違ってそれを使用しています）：

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

私は正しい軌道に乗って何が行方不明アム

おかげ

Answer 1

私は速さについて肯定的ではないんですけれどもが、これは、あなたが探しているものだと思う：

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

例コール：

ABC 
ABD 
ABE 
ACD 
ACE 
ADE 
BCD 
BCE 
BDE 
CDE 
Press any key to continue... 

：中

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

結果

Answer 2

ですから、すべてのPOSSをしたいですか？？？！ n要素の集合の中からk要素を取り出し、各k要素のリストを昇順に並べ替える必要がありますか？

こちらをご覧ください：Algorithm to return all combinations of k elements from n

Answer 3

をあなたが計算されます再帰関数を探しています：の残りの1つの少ない文字で昇順順列と連結（昇順にソート）与えられたアルファベットの最初の文字アルファベットに加えて、同じ文字数を持つ剰余の昇順の並べ替えが含まれます。

明確にするために、あなたの例のために、それはあなたがn>m => idx_{n} > idx_{m}と0 < n,m <= count(alphabet)、とは、すべての可能なインデックスを列挙することを制約してあなたのアルファベットにnインデックスを持つことができ、

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

が反復的にそれをコーディングすることです。それはいくつかの余分な条件を持つカウンタのようなものです。これらのインデックスを使用してカウントするには、1, 2, 3, 4, ...nから始めます。最後のカウンターがアルファベットの長さに達するまでインクリメントします。そのとき、インデックスがカウントより大きくならない限り、前のインデックスを見つけて1ずつ増やし、それに続くすべてのインデックスを1+idx_prevに設定します。存在する場合は、有効な位置を使い果たすまで前のインデックスで処理を繰り返します。

あなたの例のダウン簡単な実行は次のようになります。

• 初期条件：{1,2,3}
• を実行し、すべての有効な位置のための最後のインデックス：{1,2,4}、{1,2,5}
• インクリメント前のインデックス（2）次へ残りをリセットします。{1,3,4}
• すべての有効な位置の最後のインデックスを実行します。{1,3,5}
• インクリメント前のインデックス（2）次、残りをリセットすることがない可能移動：{1,4,5}
• を実行し、すべての有効な位置のための最後のインデックス：10インクリメント前のインデックス（2）次、残りをリセットしないように何の可能な動き
{2,3,4}
• を実行し、すべての有効な位置のための最後のインデックス：{2,4,5}
• ラン：（2）次、残りをリセットする{2,3,5}
• インクリメント前のインデックス
• インクリメント前のインデックス（1）は、次の残りをリセットしますすべての人の最後のインデックス有効なポジション：なし可能な動き
• インクリメント前のインデックス（2）次の残りリセットする：いいえ可能な動き
• インクリメント前のインデックス（1）次へを、残りをリセット：{3,4,5}
• 実行のための最後のインデックスすべての有効な位置：次残りをリセットしないことが可能に移動
• インクリメント前指数（2）：なし可能な移動
• インクリメント前のインデックスは（1）次に、残りをリセットしない：なし可能な移動を
を終了します

Answer 4

再帰の必要はありません。

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

Answer 5

ここで何をしたいん再帰的な方法です。

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