Program a shifting number pattern

Question

Possible Duplicate:
Generating permutations of a set (most efficiently)

I was looking at an old programming challenge, and I was trying to come up with a solution. The challenge is expired, and years old, and I'm doing it just to build skill at this point.

I need to generate numbers in the following pattern:

123456789
123456798
123456879
123456897
123456978
123456987

Continuing onward, always using the same 9 numbers, never duplicating them, and always grabbing the next one in line.

I've been wracking my brain for the last 2 hours, and can't figure out a good programming pattern to tackle this.

Any suggestions?

See: [Generating Permutations in Lexicographic Order](http://en.wikipedia.org/wiki/Permutation#Generation_in_lexicographic_order) — verdesmarald, Oct 10 '12 at 02:30

score 1 · Accepted Answer · answered Oct 10 '12 at 03:51

How about this as a solution:

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;

This turns out to be quite fast producing all of the results in 864 milliseconds on my computer.

Here are the first 10 results:

This worked out pretty slick! – Brian Deragon Oct 10 '12 at 04:21 — Brian Deragon, Oct 10 '12 at 04:21

score 0 · Answer 2 · answered Oct 10 '12 at 04:28

I did come up with two solutions:

The slow way

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

The fast way

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

Program a shifting number pattern

2 Answers2