升序列表排列

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）的长度需要是动态的，所以我想我需要某种递归......我只是不知道如何实现它。

任何帮助将不胜感激！

编辑

到目前为止，这是我有什么（我觉得我越来越近......我只是无法得到它的实际构建的最终名单（工会不工作 - 我使用它错误地）：

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

调用示例：

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... 

Answer 2

所以，你希望所有的POSS？？？！在一组n个元素中包含了k个元素，并且您希望每个k元素列表按升序排列？

到这里看看：Algorithm to return all combinations of k elements from n

Answer 3

你正在寻找一个递归函数，将计算：第一个字母在给定的字母用的剩余部分少了一个字母升序排列级联（按升序排序）字母表，加上相同字母数的余数的升序排列。

为了澄清，你的例子是

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

要反复代码时，你可以有n索引到你的字母与约束n>m => idx_{n} > idx_{m}和0 < n,m <= count(alphabet)，并列举所有可能的索引。这是一些有额外条件的柜台。为了使用这些索引进行计数，您需要从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}
• 运行的所有有效位置的最后一个索引：没有可能的行动
• 递增一个索引（2）到下一并重置休息：没有可能的行动
• 递增一个索引（1）至下一个和复位休息：{2,3,4}
• 运行的所有有效位置的最后一个索引：{2,3,5}
• 递增一个索引（2）到下一并重置休息：{2,4,5}
• 运行所有的最后一个索引有效的位置：没有可能的行动
• 递增一个索引（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(); 
    }