时间戳

首页 > 解决方案 > 生成顺序很重要的列表的powerset

c# - 生成顺序很重要的列表的powerset

问题描述

我一直在寻找一种方法来创建一个强大的字母集，基本上是为了生成任何可能的字母组合，但有点扭曲，顺序很重要，所以 ab ！= ba。我在这里遇到了一段漂亮的代码，我无耻地窃取了这些代码。这是我的整个程序：

using System;
using System.Collections.Generic;
using System.Linq;

namespace PermutationsHelper
{
    static class Program
    {
        static void Main()
        {
            var ps = GetPowerSet(new List<string>() { "a", "b" });
            foreach (var item in ps)
            {
                string[] resultArr = item.ToArray();
                string result = string.Join("", resultArr);
                Console.WriteLine(result);
            }
            Console.ReadLine();
        }
        static IEnumerable<IEnumerable<T>> GetPowerSet<T>(List<T> list)
        {
            return from m in Enumerable.Range(0, 1 << list.Count)
               select
                   from i in Enumerable.Range(0, list.Count)
                   where (m & (1 << i)) != 0
                   select list[i];
        }
    }
}

输出是：

[empty]
a
b
ab

但我正在寻找的是：

[empty]
a
b
ab
ba

关于如何最好地做到这一点的任何建议？TIA

标签： c#

解决方案

您可以使用递归方法，如答案列出字符串/整数的所有排列以获得所有可能的组合和排列，包括不同的顺序。您定义了一个方法public static ISet<string> CombinationsAndPermutations(string input)，如下所示：

  • 当输入为空时，返回一个空列表。（没事做）
  • 当输入是长度为的字符串时1，返回Set带有值string.Empty和输入字符串的 a。（递归基本情况）

对于所有其他情况，您遍历字符串的所有字符并找到此特定字符或字符串位置的解决方案。您在总结果列表中收集所有子解决方案并将其返回。伪代码将如下所示：

for all positions in the string:
    get the character at position "i"
    get the remaining string without the character at position "i"
    get the solution for the remaining string (recursive call)

    add the solution to a total list of solutions
    add the solution to a total list of solutions, but add the extracted character from position "i" at the front

return the total list

话虽如此，解决方案将如下所示：

public static ISet<string> CombinationsAndPermutations(string input) {
    if (string.IsNullOrWhiteSpace(input)) {
        return new HashSet<string>();
    }
    if (input.Length == 1) {
        return new HashSet<string> { string.Empty, input };
    }

    ISet<string> result = new HashSet<string>();
    for (int i=0; i<input.Length; i++) {
        char letter = input[i];
        string remainingBefore = input.Substring(0, i);
        string remainingAfter = input.Substring(i+1);
        string remaining = remainingBefore + remainingAfter;

        ISet<string> subResult = CombinationsAndPermutations(remaining);

        foreach (string subStr in subResult) {
            result.Add(subStr);
            result.Add(letter + subStr);
        }
    }

    return result;
}

对于示例输入“abc”，这将生成Set具有以下条目的 a：

(, a, b, ab, c, ac, bc, abc, cb, acb, ba, bac, ca, bca, cab, cba)

推荐阅读