6

如何更改下面的 C# 代码以列出所有可能的排列而不重复？例如： 2 次掷骰子的结果将产生 1,1,2，这意味着 2,1,1 不应该出现。

下面是我的代码：

string[] Permutate(int input)
{
        string[] dice;
        int numberOfDice = input;
        const int diceFace = 6;
        dice = new string[(int)Math.Pow(diceFace, numberOfDice)];
        int indexNumber = (int)Math.Pow(diceFace, numberOfDice);
        int range = (int)Math.Pow(diceFace, numberOfDice) / 6;

        int diceNumber = 1;
        int counter = 0;

        for (int i = 1; i <= indexNumber; i++)
        {
            if (range != 0)
            {
                dice[i - 1] += diceNumber + " ";
                counter++;
                if (counter == range)
                {
                    counter = 0;
                    diceNumber++;
                }
                if (i == indexNumber)
                {
                    range /= 6;
                    i = 0;
                }
                if (diceNumber == 7)
                {
                    diceNumber = 1;
                }
            }
            Thread.Sleep(1);
        }
        return dice;
    }
4

5 回答 5

4

我能想到的最简单的方法：

List<string> dices = new List<string>();
for (int i = 1; i <= 6; i++)
{
    for (int j = i; j <= 6; j++)
    {
        for (int k = j; k <= 6; k++)
        {
            dices.Add(string.Format("{0} {1} {2}", i, j, k));
        }
    }
}
于 2012-07-07T08:48:00.340 回答
1

我编写了一个类来处理处理二项式系数的常用函数，这是您的问题所属的问题类型。它执行以下任务：

  1. 将任何 N 选择 K 的所有 K 索引以良好的格式输出到文件。K-indexes 可以替换为更具描述性的字符串或字母。这种方法使得解决这类问题变得非常简单。

  2. 将 K 索引转换为已排序二项式系数表中条目的正确索引。这种技术比依赖迭代的旧已发布技术快得多。它通过使用帕斯卡三角形固有的数学属性来做到这一点。我的论文谈到了这一点。我相信我是第一个发现并发表这种技术的人，但我可能是错的。

  3. 将已排序二项式系数表中的索引转换为相应的 K 索引。

  4. 使用Mark Dominus方法计算二项式系数，它不太可能溢出并且适用于更大的数字。

  5. 该类是用 .NET C# 编写的，并提供了一种通过使用通用列表来管理与问题相关的对象（如果有）的方法。此类的构造函数采用一个名为 InitTable 的 bool 值，当它为 true 时，将创建一个通用列表来保存要管理的对象。如果此值为 false，则不会创建表。无需创建表即可执行上述 4 种方法。提供了访问器方法来访问表。

  6. 有一个关联的测试类，它显示了如何使用该类及其方法。它已经用 2 个案例进行了广泛的测试，并且没有已知的错误。

要了解此类并下载代码，请参阅制表二项式系数。

于 2012-09-26T23:07:15.107 回答
0

问题的重要部分是您想要不同的集合（无论顺序如何）。例如，掷骰子 [1, 2, 1] 等于掷骰子 [1, 1, 2]。

我敢肯定有很多方法可以给这只猫剥皮，但首先想到的是创建一个 EqualityComparer，它将以您想要的方式比较骰子列表，然后使用 LINQ Distinct()方法。

这是EqualityComparer，它取 2List<int>并表示如果元素都相等（无论顺序如何）它们相等：

    private class ListComparer : EqualityComparer<List<int>>
    {
        public override bool Equals(List<int> x, List<int> y)
        {
            if (x.Count != y.Count)
                return false;
            x.Sort();
            y.Sort();
            for (int i = 0; i < x.Count; i++)
            {
                if (x[i] != y[i])
                    return false;
            }
            return true;
        }
        public override int GetHashCode(List<int> list)
        {
            int hc = 0;
            foreach (var i in list)
                hc ^= i;
            return hc;
        }
    }

这是使用它的代码。我正在使用 LINQ 来构建所有组合的列表......你也可以使用嵌套for循环来做到这一点，但出于某种原因我更喜欢这样：

    public static void Main()
    {
        var values = new[] { 1,2,3,4,5,6 };
        var allCombos = from x in values
                        from y in values
                        from z in values
                        select new List<int>{ x, y, z };
        var distinctCombos = allCombos.Distinct(new ListComparer());

        Console.WriteLine("#All combos: {0}", allCombos.Count());
        Console.WriteLine("#Distinct combos: {0}", distinctCombos.Count());
        foreach (var combo in distinctCombos)
            Console.WriteLine("{0},{1},{2}", combo[0], combo[1], combo[2]);
    }

希望有帮助！

于 2012-07-07T13:10:09.453 回答
0

Here is generic c# version using recursion (basically the recursive method takes number of dices or number of times the dice has been tossed) and returns all the combinations strings ( for ex, for '3' as per the question - there will be 56 such combinations).

public string[] GetDiceCombinations(int noOfDicesOrnoOfTossesOfDice)
        {
            noOfDicesOrnoOfTossesOfDice.Throw("noOfDicesOrnoOfTossesOfDice",
                n => n <= 0);
            List<string> values = new List<string>();
            this.GetDiceCombinations_Recursive(noOfDicesOrnoOfTossesOfDice, 1, "",
                values);
            return values.ToArray();
        }
        private void GetDiceCombinations_Recursive(int size, int index, string currentValue,
            List<string> values)
        {
            if (currentValue.Length == size)
            {
                values.Add(currentValue);
                return;
            }
            for (int i = index; i <= 6; i++)
            {
                this.GetDiceCombinations_Recursive(size, i, currentValue + i, values);
            }
        }

Below are corresponding tests...

[TestMethod]
        public void Dice_Tests()
        {
            int[] cOut = new int[] { 6, 21, 56, 126 };
            for(int i = 1; i<=4; i++)
            {
                var c = this.GetDiceCombinations(i);
                Assert.AreEqual(cOut[i - 1], c.Length);
            }
        }
于 2014-08-08T16:01:36.640 回答
0

我的数学也很差，这可能有用也可能没有帮助......

程序.cs

namespace Permutation
{
    using System;
    using System.Collections.Generic;

    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine("Generating list.");

            var dice = new List<ThreeDice>();

            for (int x = 1; x <= 6; x++)
            {
                for (int y = 1; y <= 6; y++)
                {
                    for (int z = 1; z <= 6; z++)
                    {
                        var die = new ThreeDice(x, y, z);

                        if (dice.Contains(die))
                        {
                            Console.WriteLine(die + " already exists.");
                        }
                        else
                        {
                            dice.Add(die);
                        }
                    }
                }
            }

            Console.WriteLine(dice.Count + " permutations generated.");

            foreach (var die in dice)
            {
                Console.WriteLine(die);
            }

            Console.ReadKey();
        }
    }
}

三骰子.cs

namespace Permutation
{
    using System;
    using System.Collections.Generic;

    public class ThreeDice : IEquatable<ThreeDice>
    {
        public ThreeDice(int dice1, int dice2, int dice3)
        {
            this.Dice = new int[3];
            this.Dice[0] = dice1;
            this.Dice[1] = dice2;
            this.Dice[2] = dice3;
        }

        public int[] Dice { get; private set; }

        // IEquatable implements this method. List.Contains() will use this method to see if there's a match.
        public bool Equals(ThreeDice other)
        {
            // Get the current dice values into a list.
            var currentDice = new List<int>(this.Dice);

            // Check to see if the same values exist by removing them one by one.
            foreach (int die in other.Dice)
            {
                currentDice.Remove(die);
            }

            // If the list is empty, we have a match.
            return currentDice.Count == 0;
        }

        public override string ToString()
        {
            return "<" + this.Dice[0] + "," + this.Dice[1] + "," + this.Dice[2] + ">";
        }
    }
}

祝你好运。

于 2012-07-07T08:22:15.673 回答