c# - 编写一个移位数字模式

Question

可能重复：
生成集合的排列（最有效）

我正在研究一个古老的编程挑战，并试图想出一个解决方案。挑战已经过时了，而且已经有好几年了，我这样做只是为了培养技能。

我需要按以下模式生成数字：

• 123456789
• 123456798
• 123456879
• 123456897
• 123456978
• 123456987

继续前进，始终使用相同的 9 个数字，从不重复它们，并始终抓住下一个数字。

在过去的 2 个小时里，我一直在绞尽脑汁，想不出一个好的编程模式来解决这个问题。

有什么建议么？

Answer 1

作为解决方案如何：

var numerals = Enumerable.Range(1, 9).ToArray();

var query =
    from n1 in numerals
    from n2 in numerals.Except(new [] { n1, })
    from n3 in numerals.Except(new [] { n1, n2, })
    from n4 in numerals.Except(new [] { n1, n2, n3, })
    from n5 in numerals.Except(new [] { n1, n2, n3, n4, })
    from n6 in numerals.Except(new [] { n1, n2, n3, n4, n5, })
    from n7 in numerals.Except(new [] { n1, n2, n3, n4, n5, n6, })
    from n8 in numerals.Except(new [] { n1, n2, n3, n4, n5, n6, n7, })
    from n9 in numerals.Except(new [] { n1, n2, n3, n4, n5, n6, n7, n8, })
    select n1 * 100000000
        + n2 * 10000000
        + n3 * 1000000
        + n4 * 100000
        + n5 * 10000
        + n6 * 1000
        + n7 * 100
        + n8 * 10
        + n9;

事实证明，这在我的计算机上在 864 毫秒内生成所有结果的速度非常快。

以下是前 10 个结果：

123456789 
123456798 
123456879 
123456897 
123456978 
123456987 
123457689 
123457698 
123457869 
123457896 

Answer 2

我确实提出了两个解决方案：

缓慢的方式

private static void GetAnswerByLoopingNumbers(Stopwatch timer) 
{
    int _counter = 1;
    for (int number = 123456789; number <= 987654321; number += 9)
    {
        string numToCheck = number.ToString();
        if (ContainsZero(numToCheck) || ContainsDuplicates(numToCheck))
            continue;
        _counter++;
        if (_counter != 100000)
            continue;
        timer.Stop();
        CheckAnswer(numToCheck, timer);
        break;
    } }

private static bool ContainsDuplicates(IEnumerable<char> numToCheck)
{
    IEnumerable<char> check = numToCheck as char[] ?? numToCheck.ToArray();
    foreach (char number in check)
    {
        int count = 0;
        foreach (char c in check)
        {
            if (c == number)
                count++;
        }
        if (count > 1)
            return true;
    }
    return false;
}

private static bool ContainsZero(IEnumerable<char> numToCheck)
{
    foreach (char number in numToCheck)
    {
        if (number == '0')
            return true;
    }
    return false;
}

快速的方法

private static void GetAnswerByCreatingPermutations(Stopwatch timer)
{
    int _counter = 1;
    int[] baseNumberSet = new[] { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
    while (_counter < 100000)
    {
        int firstSwapNumber = GetFirstNumberToSwap(baseNumberSet);
        int secondSwapNumber = GetSecondSwapNumber(firstSwapNumber, baseNumberSet);
        if (baseNumberSet[firstSwapNumber] >= baseNumberSet[secondSwapNumber])
            continue;
        SwapNumbers(firstSwapNumber, secondSwapNumber, baseNumberSet);
        ReverseSequenceOfNumbersAfterFirstSwapNumber(firstSwapNumber, baseNumberSet);
        _counter++;
    }
}

private static int GetFirstNumberToSwap(int[] baseNumberSet)
{
    int largestIndex = 0;

    // Check first 8 numbers
    for (int index = 0; index < 8; index++)
    {
        // Check to see if current number, is less than the next number
        if (baseNumberSet[index] < baseNumberSet[index + 1])
            largestIndex = index;
    }
    // Return the last number in sequence, to be smaller than the next number in the sequence
    return largestIndex;
}

private static int GetSecondSwapNumber(int firstSwapNumber, int[] baseNumberSet)
{
    int secondLargestIndex = 0;

    // Check all nine numbers
    for (int index = 0; index < 9; index++)
    {
        // Check to see if number is bigger than first swap number
        if (baseNumberSet[firstSwapNumber] < baseNumberSet[index])
            secondLargestIndex = index;
    }
    // Return last number in sequence that is larger than the first swap number
    return secondLargestIndex;
}

private static void ReverseSequenceOfNumbersAfterFirstSwapNumber(int firstSwapNumber, int[] baseNumberSet)
{
    if (firstSwapNumber >= 7)
        return;
    int lengthOfSequenceToSwap = 8 - firstSwapNumber;
    if (lengthOfSequenceToSwap <= 1)
        return;
    Array.Reverse(baseNumberSet, firstSwapNumber + 1, lengthOfSequenceToSwap);
}

private static void SwapNumbers(int firstSwapNumber, int secondSwapNumber, int[] baseNumberSet)
{
    baseNumberSet[firstSwapNumber] ^= baseNumberSet[secondSwapNumber];
    baseNumberSet[secondSwapNumber] ^= baseNumberSet[firstSwapNumber];
    baseNumberSet[firstSwapNumber] ^= baseNumberSet[secondSwapNumber];
}