c# - C＃で配列要素のすべての可能な組み合わせを生成する動的ネストループ

Question

同様の質問についてstackoverflowとWebを検索しましたが、必要な解決策が見つかりませんでした。

コードリストジェネレーターをプログラミングしています。

たとえば、のような文字のリストがありList<char> { 'a', 'b', 'c' };ます。

とのよう(int)minLengthな設定がいくつかあります。2(int)maxLength3

そして、私はこの出力が欲しい:

aa
ab
ac
ba
bb
bc
ca
cb
cc

aaa
aab
aac
aba
abb
abc
aca
acb
acc

baa
bab
bac
bba
bbb
bbc
bca
bcb
bcc

caa
cab
cac
cba
cbb
cbc
cca
ccb
ccc

一般的には、多次元ループを作成するだけですが、minLength、maxLength、charList の値が異なるため、これを動的に行う必要があります。

だから私はこの例のような「自己呼び出し関数」を使っていました:

    private void loop() {
        for( int i = 0; i < num; i++ ) {
            // stuff
            loop();
        }
    }

これまでのところ、次の一連のコードを作成しましたが、この段階で行き詰まります... :

    Thread mainThread;

    List<char> azlower;
    List<char> azupper;
    List<char> nullnine;

    List<char> totalChars;

    int totalNum;

    int levelCounter;

    bool running;

    public Form1() {
        InitializeComponent();
    }

    private void init() {
        azlower = new List<char> { 'a', 'b', 'c' , 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z' };
        azupper = new List<char> { 'A', 'B', 'C' , 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z' };
        nullnine = new List<char> { '0', '1', '2' /* , '3', '4', '5', '6', '7', '8', '9' */ };

        totalChars = new List<char> ();

        running = false;
    }

    private void button1_Click( object sender, EventArgs e ) {
        if( !running ) {
            init();

            // Start
            if( checkBoxAZ1.Checked ) {
                foreach( char character in azlower ) {
                    totalChars.Add( character );
                }
            }
            if( checkBoxAZ2.Checked ) {
                foreach( char character in azupper ) {
                    totalChars.Add( character );
                }
            }
            if( checkBox09.Checked ) {
                foreach( char character in nullnine ) {
                    totalChars.Add( character );
                }
            }
            if( checkBoxS.Checked && textBoxSpec.Text != "" ) {
                char[] specArray = textBoxSpec.Text.ToCharArray();
                foreach( char character in specArray ) {
                    totalChars.Add( character );
                }
            }
            totalNum = totalChars.Count;
            levelCounter = Int32.Parse( textBoxMinLength.Text );
            mainThread = new Thread( new ThreadStart( run ) );
            button1.Text = "Stop";
            running = true;
            mainThread.Start();
        } else {
            mainThread.Abort();
            button1.Text = "Start";
            running = false;
        }
    }

    private void run() {
        for( int i = 0; i < totalNum; i++ ) {
            Invoke( ( MethodInvoker ) delegate {
                write( totalChars[ i ].ToString() );
                if( i == totalNum - 1 && levelCounter == Int32.Parse( textBoxMaxLength.Text ) ) {
                    write( "\n" );
                }
            } );
            if( levelCounter < Int32.Parse( textBoxMaxLength.Text ) ) {
                levelCounter++;
                run();
            }
        }
        return;
    }

    private void write( string line ) {
        richTextBox1.Text += line;
    }

しかし、上記のセットアップと私のコードでは、出力は次のようになります。

aabc
bc

私はちょうど考え違いをしたと思いますね。

みんな、私に何か提案はありますか？

私はデカルト積も見ましたが、1つの配列だけでは機能しないと思いました...

任意の助けのためのthx。

Answer 1

これは、再帰を使用して生成する例です。

IEnumerable<string> GenerateCode(int length, int min, IEnumerable<char> chars)
{
    if (length == 0)
    {
        yield return string.Empty;
        yield break;
    }

    foreach (var mid in GenerateCode(length - 1, min, chars))
    {
        foreach (var c in chars)
        {
            var t = mid + c;
            if (length >= min)
                Console.WriteLine(t); // replace with where you want to put the results

            yield return t;
        }
    }
}

// now call this method:
GenerateCode(3 /*max length*/, 2 /*min length*/, new [] { 'a', 'b', 'c'  });

しかし、これが演習でない限り、考えられるすべてのバリエーションを生成するのはなぜでしょうか? 実際の要件を提供すれば、より良い解決策があるかもしれません。

Answer 2

public static IEnumerable<IEnumerable<T>> Permutations<T>(IEnumerable<T> source)
{
    if (source == null)
        throw new ArgumentNullException("source");
    return permutations(source.ToArray());
}

private static IEnumerable<IEnumerable<T>> permutations<T>(IEnumerable<T> source)
{
    IEnumerable<T> enumerable = source as List<T> ?? source.ToList();
    var c = enumerable.Count();
    if (c == 1)
        yield return enumerable;
    else
        for (int i = 0; i < c; i++)
            foreach (var p in permutations(enumerable.Take(i).Concat(enumerable.Skip(i + 1))))
                yield return enumerable.Skip(i).Take(1).Concat(p);
}

private static IEnumerable<string> Subsets(char[] chars)
{
    List<string> subsets = new List<string>();

    for (int i = 1; i < chars.Length; i++)
    {
        subsets.Add(chars[i - 1].ToString(CultureInfo.InvariantCulture));
        int i1 = i;
        List<string> newSubsets = subsets.Select(t => t + chars[i1]).ToList();
        subsets.AddRange(newSubsets);
    }
    subsets.Add(chars[chars.Length - 1].ToString(CultureInfo.InvariantCulture));
    return subsets;
}
private static void Main()
{
    char[] chars = new[]{'a','b','c'};
    var subsets = Subsets(chars);
    List<string> allPossibleCombPerm = 
        subsets.SelectMany(Permutations).Select(permut => string.Join("", permut)).ToList();
    allPossibleCombPerm.ForEach(Console.WriteLine);
}

Answer 3

バックトラッキング アルゴリズムを使用できます。コードは以下のとおりです。コードの動作を証明する出力も含まれています。

パラメータをスレッドに渡す必要がある場合は、この回答を参照してください。

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

namespace ConsoleApplication1
{
    class Program
    {
        const int MIN_LENGTH = 2;
        const int MAX_LENGTH = 3;
        static IList<string> vals;
        static IList<string> results;

    static void go(string cur)
    {
        if (cur.Length > MAX_LENGTH)
        {
            return;
        }
        if (cur.Length >= MIN_LENGTH && cur.Length <= MAX_LENGTH)
        {
            results.Add(cur);
        }

        foreach (string t in vals)
        {
            cur += t;
            go(cur);
            cur = cur.Substring(0, cur.Length - 1);
        }
    }
    static int Main(string[] args)
    {
        vals = new List<string>();
        vals.Add("a");
        vals.Add("b");
        vals.Add("c");

        results = new List<string>();
        go("");
        results = results.OrderBy(x => x.Length).ToList();

        foreach (string r in results)
        {
            Console.WriteLine(r);
        }

        return 0;
    }
}

出力

aa
ab
ac
ba
bb
bc
ca
cb
cc
aaa
aab
aac
aba
abb
abc
aca
acb
acc
baa
bab
bac
bba
bbb
bbc
bca
bcb
bcc
caa
cab
cac
cba
cbb
cbc
cca
ccb
ccc