升序排列

本文关键字：排列 升序 | 更新日期: 2023-09-27 18:30:06

我正在尝试获取列表的所有预定义长度排列，仅按升序排列。

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;

其中内部的"List"将是类似于"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;
    }

我走对了吗？我错过了什么？

谢谢！

升序排列

所以你想要一组n个元素中所有可能的k元素，并且你想要按升序列出每个k元素列表？

看看这里：从n 返回k个元素的所有组合的算法

我认为这就是你想要的，尽管我对速度不乐观：

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

不需要递归。

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

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

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

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

要对其进行迭代编码，可以在具有约束条件n>m => idx_{n} > idx_{m}和0 < n,m <= count(alphabet)的字母表中设置n索引，并枚举所有可能的索引。这是一个有一些额外条件的计数器。为了使用这些索引进行计数，请从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）增加到下一个，并重置其余索引：不可能移动
  • 终止

这里有一个递归方法，可以执行您想要的操作：

    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();
    }
相关文章：