c # выводит возможные маршруты - PullRequest
Новая
       1

c # выводит возможные маршруты

0 голосов
/ 09 марта 2012

У меня есть динамический массив, содержащий, например, (int) {1, 2, 3}

Я хотел бы создать следующее:

123 132 213 231 312 321

(обратите внимание на сортировку)

Я думал о создании 3 циклов для вышеперечисленного, но это решение не подходит, например, когда длина массива равна 16, и мне нужно динамическое решение.

Можете ли вы помочь?Спасибо.Это для личного проекта.

Ответы [ 2 ]

2 голосов
/ 09 марта 2012

Вы говорите о перечислении всех перестановок массива в лексикографическом порядке. Предположим сначала, что у нас есть перестановка, и мы хотим создать такую, которая будет следующей лексикографически. Вот шаги, которые мы должны предпринять (здесь a относится к переменной массива):

  1. Найти наибольшее i, для которого a[i] < a[i+1].
  2. Найдите наибольшее значение j, для которого a[i] < a[j].
  3. Обмен a[i] с a[j].
  4. Обратные элементы между a[i+1] и a[n-1] (включая оба).

Теперь, начиная с первой перестановки (которая в основном является отсортированным массивом), мы можем производить все перестановки одну за другой, используя эти шаги каждый раз, пока нам не удалось найти i на первом этапе. Когда это происходит, это означает, что мы только что создали лексикографически последнюю перестановку.

Обновление : Вот пример кода - функция, которая принимает массив, представляющий перестановку, и генерирует (и печатает) следующий лексикографически. 

/// <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;
}
2 голосов
/ 09 марта 2012

Вы можете использовать Метод расширения перестановок из превосходного EvenMoreLINQ проекта .

Пример: 

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

Выход: 

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