-1

重複の可能性:
特定の文字列のセットを入力する方法

文字列の順列を入力しようとしています。たとえば、文字列 "123" は 123 132 213 231 321 312 を与えるはずです コードを修正するには助けが必要です

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

namespace TestAAD
{
class Program
{
    static int len = 0;
    static int lenPerm = 0;
    private static void Permutations(string str, string perm , int i)
    {
        if (i == len) Console.WriteLine(perm);
        for (int k = 0; k < len; k++)
        {
             lenPerm = perm.Length;
            for (int j = 0; j < lenPerm; j++)
            {
                if ((perm[j] == str[(len - 1) - k]) && (len-1-k>0))
                    k++;
            }
            if((len-1-k) >=0)
            Permutations(str, perm + str[(len - 1) - k], i++);
        }
    }
    static void Main(string[] args)
    {
        string st = "123";
        len = st.Length;
        Permutations(st, "",0);
    }
}
}

誰かが私を助けることができれば、お願いします

4

2 に答える 2

1

PermutationsPermutationsループlen回で再度呼び出します。この 2 番目のPermutations呼び出しはPermutations、ループlen時間で再度呼び出します。これは、無限に、または少なくともスタック オーバーフローが発生するまで、何度も何度も発生します。

再帰呼び出しを使用する場合、再帰がどこかで停止することを常に確認する必要があります。

If (job not done) {
    make recursive call
}

再帰呼び出しは、ジョブの完了に向けて一歩を踏み出す必要があります。そうしないと、ジョブは決して終了しません。

UPDATE 1 (例外の問題のみに対処)

メソッドが読みにくい。式を数回繰り返す代わりにlen-1-k、ループを逆にします。代わりに、内側のループでwithfor (int k = str.Length - 1; k >= 0; k--)を減らします。また、余分な変数を取り除きました。kk--len

あなたの実装len-1-kでは常に>= 0です。したがって、再帰呼び出しは決して終了しません。そのため、減少条件を変更しましたk。kすでに であっても減少し0ます。str[k]条件の範囲外のインデックスを取得しないようにするには、k >= 0最初にチェックする必要があります。

private static void Permutations(string str, string perm, int i)
{
    if (i == str.Length)
        Console.WriteLine(perm);
    for (int k = str.Length - 1; k >= 0; k--) {
        int lenPerm = perm.Length;
        for (int j = 0; j < lenPerm; j++) {
            if (k >= 0 && perm[j] == str[k])
                k--;
        }
        if (k >= 0)
            Permutations(str, perm + str[k], i++);
    }
}

public static void Start()
{
    string st = "123";
    Permutations(st, "", 0);
}

これにより、無限の再帰は生成されなくなりましたが、結果はまだ正しくありません。コードをさらに改善する方法を理解させます。

UPDATE 2 (正しい順列の作成)

最後に、これが私の実用的な実装です

public static class PermutationBuilder
{
    private static char[] _characters;
    private static List<string> _list;

    public static IEnumerable<string> GetPermutations(string characters)
    {
        _characters = characters.ToCharArray();
        _list = new List<string>();
        AddPermutations("", 0);
        return _list;
    }

    private static void AddPermutations(string permutation, int level)
    {
        if (level >= _characters.Length) {
            _list.Add(permutation);
        } else {
            for (int i = 0; i < _characters.Length; i++) {
                char ch = _characters[i];
                if (ch != ' ') {
                    _characters[i] = ' ';
                    AddPermutations(permutation + ch, level + 1);
                    _characters[i] = ch;
                }
            }
        }
    }
}

スペース文字で使用されている文字を一時的にマークしていることに注意してください。

あなたはそれをこのように呼びます

foreach (string permutation in PermutationBuilder.GetPermutations("123")) {
    Console.WriteLine(permutation);
}
于 2012-12-08T15:59:47.053 に答える
1

置換は非常に簡単です。

public string[] FindPermutations(string word)
{
    if (word.Length == 2)
    {
        char[] c = word.ToCharArray();
        string s = new string(new[] { c[1], c[0] });
        return new[]
            {
                word,
                s
            };
    }

    List<string> result = new List<string>();

    string[] subsetPermutations = FindPermutations(word.Substring(1));
    char firstChar = word[0];
    foreach (string temp in subsetPermutations
                    .Select(s => firstChar.ToString(CultureInfo.InvariantCulture) + s))
    {
        result.Add(temp);
        char[] chars = temp.ToCharArray();
        for (int i = 0; i < temp.Length - 1; i++)
        {
            char t = chars[i];
            chars[i] = chars[i + 1];
            chars[i + 1] = t;
            string s2 = new string(chars);
            result.Add(s2);
        }
    }
    return result.ToArray();
}
于 2012-12-08T16:02:29.847 に答える