带有递归的重复算法的排列

Question

我在使用一个函数而不是使用多个函数来使其工作时遇到一些麻烦。

如果我想获得像 2^3 这样的重复排列。 重复排列

获得：

000
001
101
011
100
101
110
111

我可以有这个功能：

   static void Main(string[] args)
    {
        three_permutations(2);
        Console.ReadLine();
    }


    static void three_permutations(int y)
    {

        for (int aa = 0; aa < y; aa++)
        {
            for (int bb = 0; bb < y; bb++)
            {
                for (int cc = 0; cc < y; cc++)
                {
                    Console.Write((aa));
                    Console.Write((bb));
                    Console.Write((cc));
                    Console.WriteLine();
                }
            }
        }

    }

但是要做4（比如2^4），我能想到的唯一方法是这样的：

  static void four_permutations(int y)
    {
            for (int aa = 0; aa < y; aa++)
            {
                for (int bb = 0; bb < y; bb++)
                {
                    for (int cc = 0; cc < y; cc++)
                    {
                        for (int dd = 0; dd < y; dd++)
                        {
                            Console.Write((aa));
                            Console.Write((bb));
                            Console.Write((cc));
                            Console.Write((dd));
                            Console.WriteLine();
                        }
                    }
                }
            }
     }

但我确信有更好的方法使用递归，我只是不知道该怎么做。我很感激任何帮助。谢谢。

Answer 1

void permutations(string text, int numberOfDigits, int numberOfChars)
{
    if (numberOfDigits > 0)
        for (int j = 0; j < numberOfChars; j++)
            permutations(text + j.ToString(), numberOfDigits - 1, numberOfChars);
    else textBox1.Text += text + "\r\n";
}

并致电：

permutations("", 3, 2);

Answer 2

重复排列本质上是在另一个基数中计数。

public static void Permutations(int digits, int options)
{
    double maxNumberDouble = Math.Ceiling(Math.Pow(options, digits));
    int maxNumber = (int)maxNumberDouble;
    for (int i = 0; i < maxNumber; i++)
    {
        Console.WriteLine(Convert.ToString(i, options).PadLeft(3, '0'));
    }
}

您打印的示例本质上是以 2 为基数从 0 数到 8。

Answer 3

无需递归，并列出供以后使用，不到 10 行。

public IEnumerable<List<int>> YieldCombinationsOfN(int places, int digitMin, int digitMax)
{            
    int n = digitMax - digitMin + 1;
    int numericMax = (int)Math.Pow(n, places);

    for (int i = 0; i < numericMax; i++)
    {
        List<int> li = new List<int>(places);
        for(int digit = 0; digit < places; digit++)
        {
            li.Add(((int)(i / Math.Pow(n, digit)) % n) + digitMin);
        }
        yield return li;
    }
}

Answer 4

这是另一个答案，它不依赖于递归或 Pow 等数学运算符，但尽可能简单：

    static IEnumerable<int[]> permute(int size)
    {
        int[] i = new int[size];
        while (true) {
            yield return i;
            int index = 0;
            while (index < size) {
                i[index]++;
                if (i[index] == size) {
                    i[index] = 0;
                    index++;
                }
                else break;
            }
            if (index == size) break;
        }
    }

    static void Main(string[] args)
    {
        foreach (int[] i in permute(3))
        {
            foreach (int j in i) { Console.Write(j + " "); }
            Console.WriteLine();
        }
    }