如何在C#中为给定的字符串键入置换 [英] how to type Permutation for a given string in C#

问题描述

可能重复:
如何为给定字符串键入集合

Possible Duplicate:
How to type sets for a given string

我正在尝试输入字符串的排列 例如字符串"123"应该给我 123132213231321312 我需要帮助来修复我的代码

I'm trying to type the permutation for a string for example the string "123" should give me 123 132 213 231 321 312 I need help to fix my code

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);
    }
}
}

请任何人可以帮助我，请 谢谢大家

Please if anyone can help me , Please thanks all

推荐答案

Permutations循环len次再次调用Permutations.第二次Permutations调用再次循环len次调用Permutations.这一次又一次地无休止地发生，或者至少直到堆栈溢出为止.

Permutations calls Permutations again in a loop len times. This second Permutations call calls Permutations again in a loop len times. This happens again and again endlessly, or at least until you get a stack overflow.

使用递归调用时，必须始终确保递归在某处停止.

When you use recursive calls, you always must make sure that the recursion stops somewhere.

If (job not done) {
    make recursive call
}

递归调用必须朝着完成工作迈出一步，否则它将永远无法完成.

The recursive call must make a step towards the completion of the job, otherwise it will never finish.

更新1 (仅解决异常问题)

该方法难以阅读.不必重复几次表达len-1-k，而是要反转循环！ for (int k = str.Length - 1; k >= 0; k--)并在内部循环中使用k--减小k.我也摆脱了多余的变量len.

The method is difficult to read. Instead of repeating the expression len-1-k several times, reverse the loop! for (int k = str.Length - 1; k >= 0; k--) and decrease k with k-- instead in the inner loop. I also got rid of the variable len which is superfluous.

在您的实现中，len-1-k始终为>= 0.因此，递归调用将永远不会结束.因此，我更改了减小k的条件.即使它已经是0，它也会减小k.为了不使str[k]中的索引超出范围错误，必须首先检查条件k >= 0.

In your implementation len-1-k is always >= 0. Therefore the recursive calls will never end. Therefore I changed the condition for decreasing k. It will decrease k even if it is already 0. In order not the get an index out of bounds error in str[k] the condition k >= 0 must be checked first.

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);
}

这不再产生无限递归，但结果仍然不正确.我让您知道如何进一步改善代码.

This doesn't produce an endless recursion any more but the result is still not correct. I let you figure out how to improve the code further.

更新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;
                }
            }
        }
    }
}

请注意，我会暂时标记已使用空格字符的字符.

Note that I temporarily mark the characters that have been used with a space character.

您这样称呼

foreach (string permutation in PermutationBuilder.GetPermutations("123")) {
    Console.WriteLine(permutation);
}

这篇关于如何在C#中为给定的字符串键入置换的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！