4

我试图允许用户在文本框中输入文本,并让程序生成它的所有可能组合,除了最少 3 个字符和最多 6 个字符。我不需要像“as”这样的无用词, 'a'、'i'、'to' 等使我的数组变得混乱。我还将根据字典检查每个组合,以确保它是一个真实的单词。

我有完整的字典(精心生成,这里有一个链接作为回报(警告:巨大的加载时间(对我来说)!)

无论如何,如果用户输入“ABCDEF”(没有特别的顺序),我怎么能生成,例如:

'ABC'
'BAC'
'CAB'
...
'ABD'
'ABE'
'ABF'

等等......每一种可能的组合,不管什么顺序?我知道这些组合的数量很多,但只需要计算一次,所以我不太担心。

我发现代码示例可以递归地查找固定宽度字符串(ABCDEF、ABCDFE ... ACDBFE 等)的组合(不是排列,我不需要那些)。他们没有做我需要的事情,我什至不知道从哪里开始这个项目。

这不是家庭作业,它开始是我的一个个人项目,它逐渐占据了我的生活,解决了一个如此简单的问题......我不敢相信我无法解决这个问题!

4

4 回答 4

2

听起来你在描述Power Set

这是我在我的个人图书馆周围的一个实现:

// Helper method to count set bits in an integer
public static int CountBits(int n)
{
    int count = 0;
    while (n != 0)
    {
        count++;
        n &= (n - 1);
    }
    return count;
}


public static IEnumerable<IEnumerable<T>> PowerSet<T>(
    IEnumerable<T> src, 
    int minSetSize = 0, 
    int maxSetSize = int.MaxValue)
{
    // we want fast random access to the source, so we'll
    // need to ToArray() it
    var cached = src.ToArray();
    var setSize = Math.Pow(2, cached.Length);
    for(int i=0; i < setSize; i++)
    {
        var subSetSize = CountBits(i);
        if(subSetSize < minSetSize || 
           subSetSize > maxSetSize)
        {
            continue;
        }
        T[] set = new T[subSetSize];

        var temp = i;
        var srcIdx = 0;
        var dstIdx = 0;
        while(temp > 0)
        {
            if((temp & 0x01) == 1)
            {
                set[dstIdx++] = cached[srcIdx];
            }
            temp >>= 1;
            srcIdx++;            
        }
        yield return set;
    }
    yield break;
}

还有一个快速测试台:

void Main()
{
    var src = "ABCDEF";
    var combos = PowerSet(src, 3, 6);

    // hairy joins for great prettiness
    Console.WriteLine(
        string.Join(" , ", 
            combos.Select(subset => 
                string.Concat("[", 
                    string.Join(",", subset) , "]")))
    );
}

输出:

[A,B,C] , [A,B,D] , [A,C,D] , [B,C,D] , [A,B,C,D] , [A,B,E] , [A,C,E] , [B,C,E] , [A,B,C,E] , 
[A,D,E] , [B,D,E] , [A,B,D,E] , [C,D,E] , [A,C,D,E] , [B,C,D,E] , [A,B,C,D,E] , [A,B,F] , 
[A,C,F] , [B,C,F] , [A,B,C,F] , [A,D,F] , [B,D,F] , [A,B,D,F] , [C,D,F] , [A,C,D,F] , 
[B,C,D,F] , [A,B,C,D,F] , [A,E,F] , [B,E,F] , [A,B,E,F] , [C,E,F] , [A,C,E,F] , [B,C,E,F] , 
[A,B,C,E,F] , [D,E,F] , [A,D,E,F] , [B,D,E,F] , [A,B,D,E,F] , [C,D,E,F] , [A,C,D,E,F] , 
[B,C,D,E,F] , [A,B,C,D,E,F]
于 2013-02-27T04:21:47.360 回答
0

假设,您还想要“AAB”之类的东西,您的一组字母的“叉积”应该是它。

生成可以像 LINQ 一样简单:

            string myset = "ABCDE";
            var All = (from char l1 in myset 
                   from char l2 in myset 
                   from char l3 in myset 
                   select new string(new char[] { l1, l2, l3})).ToList();

注意:构造许多字符串和字符数组并不快。您可能希望用自定义类替换新字符串和新字符 [],如下所示:

select new MyCustomClass(l1, l2, l3).ToList();

如果您不想要“AAB”(或“EEL”)之类的东西,那么我会将您指向维基百科的“组合”。

要从固定长度变为“从 3 到 6 的任何长度”,请加入多个集合,如果限制是动态的,则使用循环。

于 2013-02-27T03:28:10.103 回答
0

最好的方法是使用 for 循环并将每个字符从 int 转换为 char 并将它们连接在一起形成一个字符串。

例如:

for(int i = 0; i < 26; i++)
{
    Console.WriteLine((char)i + 'A');        
}
于 2013-02-27T03:29:06.050 回答
0

从这个链接(在麻省理工学院许可下)

using System;
using System.Collections.Generic;
using System.Diagnostics;

// Copyright (c) 2010 Alex Regueiro
// Licensed under MIT license, available at <http://www.opensource.org/licenses/mit-license.php>.
// Published originally at <http://blog.noldorin.com/2010/05/combinatorics-in-csharp/>.
// Version 1.0, released 22nd May 2010.
public static class CombinatoricsUtilities
{
    // Error messages
    private const string errorMessageValueLessThanZero = "Value must be greater than zero, if specified.";
    private const string errorMessagesIndicesListInvalidSize = "List of indices must have same size as list of elements.";

    /// <summary>
    /// Gets all permutations (of a given size) of a given list, either with or without reptitions.
    /// </summary>
    /// <typeparam name="T">The type of the elements in the list.</typeparam>
    /// <param name="list">The list of which to get permutations.</param>
    /// <param name="action">The action to perform on each permutation of the list.</param>
    /// <param name="resultSize">The number of elements in each resulting permutation; or <see langword="null"/> to get
    /// premutations of the same size as <paramref name="list"/>.</param>
    /// <param name="withRepetition"><see langword="true"/> to get permutations with reptition of elements;
    /// <see langword="false"/> to get permutations without reptition of elements.</param>
    /// <exception cref="ArgumentNullException"><paramref name="list"/> is <see langword="null"/>. -or-
    /// <paramref name="action"/> is <see langword="null"/>.</exception>
    /// <exception cref="ArgumentException"><paramref name="resultSize"/> is less than zero.</exception>
    /// <remarks>
    /// The algorithm performs permutations in-place. <paramref name="list"/> is however not changed.
    /// </remarks>
    public static void GetPermutations<T>(this IList<T> list, Action<IList<T>> action, int? resultSize = null,
        bool withRepetition = false)
    {
        if (list == null)
            throw new ArgumentNullException("list");
        if (action == null)
            throw new ArgumentNullException("action");
        if (resultSize.HasValue && resultSize.Value <= 0)
            throw new ArgumentException(errorMessageValueLessThanZero, "resultSize");

        var result = new T[resultSize.HasValue ? resultSize.Value : list.Count];
        var indices = new int[result.Length];
        for (int i = 0; i < indices.Length; i++)
            indices[i] = withRepetition ? -1 : i - 1;

        int curIndex = 0;
        while (curIndex != -1)
        {
            indices[curIndex]++;
            if (indices[curIndex] == list.Count)
            {
                indices[curIndex] = withRepetition ? -1 : curIndex - 1;
                curIndex--;
            }
            else
            {
                result[curIndex] = list[indices[curIndex]];
                if (curIndex < indices.Length - 1)
                    curIndex++;
                else
                    action(result);
            }
        }
    }

    /// <summary>
    /// Gets all combinations (of a given size) of a given list, either with or without reptitions.
    /// </summary>
    /// <typeparam name="T">The type of the elements in the list.</typeparam>
    /// <param name="list">The list of which to get combinations.</param>
    /// <param name="action">The action to perform on each combination of the list.</param>
    /// <param name="resultSize">The number of elements in each resulting combination; or <see langword="null"/> to get
    /// premutations of the same size as <paramref name="list"/>.</param>
    /// <param name="withRepetition"><see langword="true"/> to get combinations with reptition of elements;
    /// <see langword="false"/> to get combinations without reptition of elements.</param>
    /// <exception cref="ArgumentNullException"><paramref name="list"/> is <see langword="null"/>. -or-
    /// <paramref name="action"/> is <see langword="null"/>.</exception>
    /// <exception cref="ArgumentException"><paramref name="resultSize"/> is less than zero.</exception>
    /// <remarks>
    /// The algorithm performs combinations in-place. <paramref name="list"/> is however not changed.
    /// </remarks>
    public static void GetCombinations<T>(this IList<T> list, Action<IList<T>> action, int? resultSize = null,
        bool withRepetition = false)
    {
        if (list == null)
            throw new ArgumentNullException("list");
        if (action == null)
            throw new ArgumentNullException("action");
        if (resultSize.HasValue && resultSize.Value <= 0)
            throw new ArgumentException(errorMessageValueLessThanZero, "resultSize");

        var result = new T[resultSize.HasValue ? resultSize.Value : list.Count];
        var indices = new int[result.Length];
        for (int i = 0; i < indices.Length; i++)
            indices[i] = withRepetition ? -1 : indices.Length - i - 2;

        int curIndex = 0;
        while (curIndex != -1)
        {
            indices[curIndex]++;
            if (indices[curIndex] == (curIndex == 0 ? list.Count : indices[curIndex - 1] + (withRepetition ? 1 : 0)))
            {
                indices[curIndex] = withRepetition ? -1 : indices.Length - curIndex - 2;
                curIndex--;
            }
            else
            {
                result[curIndex] = list[indices[curIndex]];
                if (curIndex < indices.Length - 1)
                    curIndex++;
                else
                    action(result);
            }
        }
    }

    /// <summary>
    /// Gets a specific permutation of a given list.
    /// </summary>
    /// <typeparam name="T">The type of the elements in the list.</typeparam>
    /// <param name="list">The list to permute.</param>
    /// <param name="indices">The indices of the elements in the original list at each index in the permuted list.
    /// </param>
    /// <returns>The specified permutation of the given list.</returns>
    /// <exception cref="ArgumentNullException"><paramref name="list"/> is <see langword="null"/>. -or-
    /// <paramref name="indices"/> is <see langword="null"/>.</exception>
    /// <exception cref="ArgumentException"><paramref name="indices"/> does not have the same size as
    /// <paramref name="list"/>.</exception>
    public static IList<T> Permute<T>(this IList<T> list, IList<int> indices)
    {
        if (list == null)
            throw new ArgumentNullException("list");
        if (indices == null)
            throw new ArgumentNullException("indices");
        if (list.Count != indices.Count)
            throw new ArgumentException(errorMessagesIndicesListInvalidSize, "indices");

        var result = new T[list.Count];
        for (int i = 0; i < result.Length; i++)
            result[i] = list[indices[i]];
        return result;
    }
}
于 2013-02-27T03:35:32.560 回答