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

您正在寻找一个递归函数，它将计算：给定字母表中的第一个字母（按升序排序）与升序排列与字母表其余部分的一个字母相连接，加上其余字母的升序排列与相同的字母数数。

为了澄清，对于你的例子，它是

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) 增加到下一个并重置其余的：没有可能的移动
  • 终止
于 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 回答