CODEWITHSUNDEEP
c#algorithmcombinationscombinatorics
Novak
Novak

Reputation: 2768

c# output possible routes

I have an dynamic array, containing for example (int) {1, 2, 3}

I would like to generate the following:

123 132 213 231 312 321

(note the sorting)

I was thinking of building 3 loops for the above, but that solution doesn't come up well when the array length is 16 for example, and I need a dynamic solution.

Can you help? Thank you. This is for a personal project.

Upvotes: 0

Views: 228

Answers (2)

Andrei
Andrei

Reputation: 56688

You are talking about listing all permutations of an array in lexicographic order. Lets assume first we have a permutation and we want to generate one that goes next lexicographically. Here are the steps we have to take (here a goes for an array variable, ):

  1. Find the largest i for which a[i] < a[i+1].
  2. Find the largest j for which a[i] < a[j].
  3. Swap a[i] with a[j].
  4. Reverse elements between a[i+1] and a[n-1] (including both).

Now starting from the first permutation (which is basically a sorted array), we can produce all permutations one by one, using these steps every time, until we failed to find i in the first step. When this happens, it means that we just produced the lexicographically last permutation.

Update: Here is the code sample - function that takes an array representing a permutation and generates (and prints) the next one lexicographically.

/// <summary>
/// Generates and prints next permutation lexicographically.
/// </summary>
/// <param name="a">An array representing a permutation.</param>
/// <returns><c>true</c> if next permutation was generated succesfully, <c>false</c> otherwise.</returns>
public bool PrintNextPermutation(int[] a)
{
    int i = a.Length - 2;
    while (i >= 0 && a[i] >= a[i + 1]) i--;

    if (i <0)
    {
        // it was the last permutation
        return false;
    }

    int j = a.Length - 1;
    while (a[i] >= a[j]) j--;

    int temp = a[i];
    a[i] = a[j];
    a[j] = temp;

    Array.Reverse(a, i + 1, a.Length - (i + 1));

    foreach (int item in a)
    {
        Console.Write(item + " ");
    }
    Console.WriteLine();

    return true;
}

Upvotes: 2

dtb
dtb

Reputation: 217293

You can use the Permutations Extension Method from the excellent EvenMoreLINQ project.

Example:

foreach (var p in new int[] { 1, 2, 3 }.Permutations())
{
    Console.WriteLine(string.Join(", ", p));
}

Output:

1, 2, 3
1, 3, 2
2, 1, 3
2, 3, 1
3, 1, 2
3, 2, 1

Upvotes: 2

Related Questions