19

一連の数字のすべての可能な組み合わせを含むリストを生成するLinqを作成することは可能ですか??

「21」と入力すると、次の要素を含むリストが生成されます。

list[0] = "21"
list[1] = "22"
list[2] = "11"
list[3] = "12"

（必ずしもこの順ではありません）

range を使用して次のようなことができることを理解しています。

List<char> letterRange = Enumerable.Range('a', 'z' - 'a' + 1).Select(i => (Char)i).ToList(); //97 - 122 + 1 = 26 letters/iterations

azからアルファベットを生成します。しかし、私はこの知識をコンビネーションジェネレーターを作るために移すことができないようです

次のコードでそれを理解することができましたが、大きすぎるようで、数行で実行できると確信しています。それは本当に私が作った悪い解決策のように感じます.

GetAllCombinations("4321")それが助けになるなら私が電話したと想像してください

public static String[] GetAllCombinations(String s)
{
    var combinations = new string[PossibleCombinations(s.Length)];

    int n = PossibleCombinations(s.Length - 1);

    for (int i = 0; i < s.Length; i++)
    {
        String sub;
        String[] subs;

        if (i == 0)
        {
            sub = s.Substring(1); //Get the first number
        }
        else if (i == s.Length - 1)
        {
            sub = s.Substring(0, s.Length - 1);
        }
        else
        {
            sub = s.Substring(0, i) + s.Substring(i + 1); 
        }

        subs = GetAllCombinations(sub);

        for (int j = 0; j < subs.Length; j++)
        {
            combinations[i * n + j] = s[i] + subs[j];
        }
    }

    return combinations;
}
public static int PossibleCombinations(int n) //Combination possibilities. e.g 1-2-3-4 have 24 different combinations
{
    int result = 1;

    for (int i = 1; i <= n; i++)
        result *= i;

    return result;
}
4

6 に答える 6

39

価値があるので、次のようなことを試してください。

public static IEnumerable<string> GetPermutations(string s)
{
    if (s.Length > 1)
        return from ch in s
               from permutation in GetPermutations(s.Remove(s.IndexOf(ch), 1))
               select string.Format("{0}{1}", ch, permutation);

    else
        return new string[] { s };
}
于 2009-04-21T21:10:09.767 に答える
32

記録のために：ジョシュの答えは一般的な方法です：

public static IEnumerable<IEnumerable<T>> GetPermutations<T>(IEnumerable<T> items) {
        if (items.Count() > 1) {
            return items.SelectMany(item => GetPermutations(items.Where(i => !i.Equals(item))),
                                   (item, permutation) => new[] { item }.Concat(permutation));
        } else {
            return new[] {items};
        }
    }
于 2011-10-13T06:59:58.683 に答える
10

これが、Linqを使用した順列と組み合わせの関数です

public static IEnumerable<TSource> Prepend<TSource>(this IEnumerable<TSource> source, TSource item)
{
    if (source == null)
        throw new ArgumentNullException("source");

    yield return item;

    foreach (var element in source)
        yield return element;
}

public static IEnumerable<IEnumerable<TSource>> Permutate<TSource>(this IEnumerable<TSource> source)
{
    if (source == null)
        throw new ArgumentNullException("source");

    var list = source.ToList();

    if (list.Count > 1)
        return from s in list
                from p in Permutate(list.Take(list.IndexOf(s)).Concat(list.Skip(list.IndexOf(s) + 1)))
                select p.Prepend(s);

    return new[] { list };
}

public static IEnumerable<IEnumerable<TSource>> Combinate<TSource>(this IEnumerable<TSource> source, int k)
{
    if (source == null)
        throw new ArgumentNullException("source");

    var list = source.ToList();
    if (k > list.Count)
        throw new ArgumentOutOfRangeException("k");

    if (k == 0)
        yield return Enumerable.Empty<TSource>();

    foreach (var l in list)
        foreach (var c in Combinate(list.Skip(list.Count - k - 2), k - 1))
            yield return c.Prepend(l);
}

DNA アルファベット「A」、「C」、「G」、「T」の場合:

var dna = new[] {'A', 'C', 'G', 'T'};

foreach (var p in dna.Permutate())
    Console.WriteLine(String.Concat(p));

与える

ACGT ACTG AGCT AGTC ATCG ATGC CAGT CATG CGAT CGTA CTAG CTGA GACT GATC GCAT GCTA GTAC GTCA TACG TAGC TCAG TCGA TGAC TGCA

および DNA アルファベットの組み合わせ (k = 2)

foreach (var c in dna.Combinate(2))
        Console.WriteLine(String.Concat(c));

それは

AA AC AG AT CA CC CG CT GA GC GG GT TA TC TG TT
于 2012-08-17T19:58:34.177 に答える
2

他の人が指摘しているように、このページのソリューションは、要素のいずれかが同じ場合に重複を生成します. Distinct() 拡張機能はそれらを削除しますが、通常は検索ツリー全体がトラバースされるため、あまりスケーラブルではありません。トラバーサル中に呼び出すことで、検索スペースを大幅にトリミングします。

private static IEnumerable<string> Permute(string str)
{
    if (str.Length == 0)
        yield return "";
    else foreach (var index in str.Distinct().Select(c => str.IndexOf(c)))
        foreach (var p in Permute(str.Remove(index, 1)))
            yield return str[index] + p;
}

文字列 "bananabana" の例では、トラバーサル カリングを行わない場合に 9,864,101 個のノードが訪問されるのに対し、8,294 個のノードが訪問されることになります。

于 2015-07-08T22:54:16.337 に答える
2

あなたが探しているのは、実際には順列です。要するに、順列は順序が重要であることを意味します (つまり、12 は 21 とは異なります) が、組み合わせは順序が無関係であることを意味します (12 と 21 は同等です)。詳細については、ウィキペディアを参照してください。

このスレッドを参照してください。

純粋な LINQ で行うことについては、LINQ を使用するために LINQ を使用しているように聞こえます。

于 2009-04-21T20:34:25.000 に答える
0

この Permute LINQ 拡張機能を使用できます。

foreach (var value in Enumerable.Range(1,3).Permute())
  Console.WriteLine(String.Join(",", value));

これにより、次のようになります。

1,1,1
1,1,2
1,1,3
1,2,1
1,2,2
1,2,3
1,3,1
1,3,2
1,3,3
2,1,1
2,1,2
2,1,3
2,2,1
2,2,2
2,2,3
2,3,1
...

オプションで順列の数を指定できます

foreach (var value in Enumerable.Range(1,2).Permute(4))
  Console.WriteLine(String.Join(",", value));

結果：

1,1,1,1
1,1,1,2
1,1,2,1
1,1,2,2
1,2,1,1
1,2,1,2
1,2,2,1
1,2,2,2
2,1,1,1
2,1,1,2
2,1,2,1
2,1,2,2
2,2,1,1
2,2,1,2
2,2,2,1
2,2,2,2

追加する拡張クラス:

public static class IEnumerableExtensions
{
  public static IEnumerable<IEnumerable<T>> Permute<T>(this IEnumerable<T> values) => values.SelectMany(x => Permute(new[] { new[] { x } }, values, values.Count() - 1));
  public static IEnumerable<IEnumerable<T>> Permute<T>(this IEnumerable<T> values, int permutations) => values.SelectMany(x => Permute(new[] { new[] { x } }, values, permutations - 1));
  private static IEnumerable<IEnumerable<T>> Permute<T>(IEnumerable<IEnumerable<T>> current, IEnumerable<T> values, int count) => (count == 1) ? Permute(current, values) : Permute(Permute(current, values), values, --count);
  private static IEnumerable<IEnumerable<T>> Permute<T>(IEnumerable<IEnumerable<T>> current, IEnumerable<T> values) => current.SelectMany(x => values.Select(y => x.Concat(new[] { y })));
}
于 2019-04-25T01:25:52.677 に答える