7

SOには、順列リストについて同様の言葉で書かれた質問がいくつかあることは知っていますが、それらは私が探しているものに完全には対応していないようです。これを行う方法があることは知っていますが、空白を描画しています。この形式に似たフラットファイルがあります。

Col1|Col2|Col3|Col4|Col5|Col6
a|b,c,d|e|f|g,h|i
. . .

ここに秘訣があります。これらの行のすべての可能な順列のリストを作成したいと思います。ここで、行のコンマ区切りのリストは可能な値を表します。たとえばIEnumerable<string>、上記を行に表すようにすると、次のようになります。

IEnumerable<string> row = new string[] { "a", "b,c,d", "e", "f", "g,h", "i" };
IEnumerable<string> permutations = GetPermutations(row, delimiter: "/");

これにより、次の文字列データのコレクションが生成されます。

a/b/e/f/g/i
a/b/e/f/h/i
a/c/e/f/g/i
a/c/e/f/h/i
a/d/e/f/g/i
a/d/e/f/h/i

これは私には再帰的な方法にエレガントに適合するように思えますが、どうやら私は月曜日の悪いケースを持っており、それにアプローチする方法について頭を悩ませることはできません。いくつかの助けをいただければ幸いです。どのGetPermutations(IEnumerable<string>, string)ように見えるべきですか？

4

4 に答える 4

1

使用できるアルゴリズムの1つは、基本的にカウントのようなものです。

  • 各リストの0番目の項目から開始します（00000）
  • 最後の値をインクリメントします（00001、00002など）
  • 1つの値を増やすことができない場合は、値をリセットして次の値（00009、000010、00011など）を増やします。
  • 値を増やすことができない場合は、これで完了です。

働き：

static IEnumerable<string> Permutations(
    string input,
    char separator1, char separator2,
    string delimiter)
{
    var enumerators = input.Split(separator1)
        .Select(s => s.Split(separator2).GetEnumerator()).ToArray();
    if (!enumerators.All(e => e.MoveNext())) yield break;

    while (true)
    {
        yield return String.Join(delimiter, enumerators.Select(e => e.Current));
        if (enumerators.Reverse().All(e => {
                bool finished = !e.MoveNext();
                if (finished)
                {
                    e.Reset();
                    e.MoveNext();
                }
                return finished;
            }))
            yield break;
    }
}

使用法：

foreach (var perm in Permutations("a|b,c,d|e|f|g,h|i", '|', ',', "/"))
{
    Console.WriteLine(perm);
}
于 2013-02-19T09:42:42.943 に答える
1

これが最もエレガントなアプローチであるかどうかはわかりませんが、始めることができるかもしれません。

private static IEnumerable<string> GetPermutations(IEnumerable<string> row, 
                                                    string delimiter = "|")
{
    var separator = new[] { ',' };
    var permutations = new List<string>();
    foreach (var cell in row)
    {
        var parts = cell.Split(separator);
        var perms = permutations.ToArray();
        permutations.Clear();
        foreach (var part in parts)
        {
            if (perms.Length == 0)
            {
                permutations.Add(part);
                continue;
            }
            foreach (var perm in perms)
            {
                permutations.Add(string.Concat(perm, delimiter, part));
            }
        }
    }
    return permutations;
}

もちろん、順列の順序が重要な場合は.OrderBy()、最後にを追加できます。

編集：alernativeを追加しました

順列を決定する前にいくつかの数値を計算することにより、文字列配列のリストを作成することもできます。

private static IEnumerable<string> GetPermutations(IEnumerable<string> row, 
                                                    string delimiter = "|")
{
    var permutationGroups = row.Select(o => o.Split(new[] { ',' })).ToArray();
    var numberOfGroups = permutationGroups.Length;
    var numberOfPermutations = 
           permutationGroups.Aggregate(1, (current, pg) => current * pg.Length);
    var permutations = new List<string[]>(numberOfPermutations);

    for (var n = 0; n < numberOfPermutations; n++)
    {
        permutations.Add(new string[numberOfGroups]);
    }

    for (var position = 0; position < numberOfGroups; position++)
    {
        var permutationGroup = permutationGroups[position];
        var numberOfCharacters = permutationGroup.Length;
        var numberOfIterations = numberOfPermutations / numberOfCharacters;
        for (var c = 0; c < numberOfCharacters; c++)
        {
            var character = permutationGroup[c];
            for (var i = 0; i < numberOfIterations; i++)
            {
                var index = c + (i * numberOfCharacters);
                permutations[index][position] = character;
            }
        }
    }

    return permutations.Select(p => string.Join(delimiter, p));
}
于 2013-02-18T22:20:19.450 に答える
1

あなたは私を「再帰的」に迎えました。別の提案があります：

private IEnumerable<string> GetPermutations(string[] row, string delimiter,
                                            int colIndex = 0, string[] currentPerm = null)
{
    //First-time initialization:
    if (currentPerm == null) { currentPerm = new string[row.Length]; }

    var values = row[colIndex].Split(',');
    foreach (var val in values)
    {
        //Update the current permutation with this column's next possible value..
        currentPerm[colIndex] = val;

        //..and find values for the remaining columns..
        if (colIndex < (row.Length - 1))
        {
            foreach (var perm in GetPermutations(row, delimiter, colIndex + 1, currentPerm))
            {
                yield return perm;
            }
        }
        //..unless we've reached the last column, in which case we create a complete string:
        else
        {
            yield return string.Join(delimiter, currentPerm);
        }
    }
}
于 2013-02-18T23:41:41.160 に答える
0

これは素晴らしい再帰関数になると本当に思っていましたが、結局そのように書かなかったのです。最終的に、これは私が作成したコードです。

public IEnumerable<string> GetPermutations(IEnumerable<string> possibleCombos, string delimiter)
{
    var permutations = new Dictionary<int, List<string>>();
    var comboArray = possibleCombos.ToArray();
    var splitCharArr = new char[] { ',' };

    permutations[0] = new List<string>();

    permutations[0].AddRange(
        possibleCombos
        .First()
        .Split(splitCharArr)
        .Where(x => !string.IsNullOrEmpty(x.Trim()))
        .Select(x => x.Trim()));

    for (int i = 1; i < comboArray.Length; i++)
    {
        permutations[i] = new List<string>();
        foreach (var permutation in permutations[i - 1])
        {
            permutations[i].AddRange(
                comboArray[i].Split(splitCharArr)
                .Where(x => !string.IsNullOrEmpty(x.Trim()))
                .Select(x => string.Format("{0}{1}{2}", permutation, delimiter, x.Trim()))
                );
        }
    }

    return permutations[permutations.Keys.Max()];
}

...私のテスト条件は、私が期待した出力を正確に提供してくれました。

IEnumerable<string> row = new string[] { "a", "b,c,d", "e", "f", "g,h", "i" };
IEnumerable<string> permutations = GetPermutations(row, delimiter: "/");
foreach(var permutation in permutations)
{
    Debug.Print(permutation);
}

これにより、次の出力が生成されました。

a/b/e/f/g/i
a/b/e/f/h/i
a/c/e/f/g/i
a/c/e/f/h/i
a/d/e/f/g/i
a/d/e/f/h/i

みんなの提案のおかげで、彼らは私の心の中で何をする必要があるかを整理するのに本当に役立ちました。私はあなたのすべての答えに賛成しました。

于 2013-02-19T15:09:43.123 に答える