Блог

Главная - Вопросы по программированию - Алгоритм минимального изменения для перестановок

Алгоритм минимального изменения для перестановок

#c# #permutation

#c# #перестановка

Вопрос:

Мой учитель дал мне этот алгоритм генерации перестановок и сказал, что это алгоритм минимального изменения. Проблема в том, что я не могу правильно его реализовать — он зацикливается вечно. Вот мой код:

 class Program
{
    private static int[] a;
    private static int[] d;
    private static int[] pos;

    public static void Swap(int[] source, int index1, int index2)
    {
        int temp = source[index1];
        source[index1] = source[index2];
        source[index2] = temp;
    }

    static void Main(string[] args)
    {
        int n = 3;
        a = new int[n   2];
        d = new int[n   2];
        pos = new int[n   2];

        for (int i = 1; i <= n;   i)
        {
            a[i] = pos[i] = i;
            d[i] = -1;
        }

        int m = 0;
        a[0] = a[n   1] = n   1;

        while (m != 1)
        {
            for (int i = 1; i <= n;   i)
            {
                Console.Write(a[i]   " ");
            }
            Console.WriteLine();

            m = n;
            while(a[pos[m] d[m]] > m)
            {
                d[m] = -d[m];
                m = m - 1;
            }

            Swap(a, a[pos[m]], a[pos[m]   d[m]]);
            Swap(pos, pos[m], pos[a[pos[m]]   d[m]]);
        }

        Console.ReadKey();
    }
}

Я искал этот алгоритм и нашел другой псевдокод, он немного отличается от первого, но он тоже не работает.
Я хотел бы использовать алгоритм Стейнхауса-Джонсона-Троттера или что-нибудь еще, и я чувствую, что данный алгоритм неверен, но учитель настаивает на том, что он правильный.

Итак, есть ли какие-либо ошибки, или я могу игнорировать учителя и использовать то, что хочу?

Комментарии:

1. Я в замешательстве от этого сообщения, вы говорите, что ваша реализация не работает, и вы чувствуете, что это неправильно, на каком основании? Может быть, ваша попытка неверна, можете ли вы написать свой собственный алгоритм или вам нужно взять тот, который дал вам ваш учитель, и реализовать его?

2. Я думаю, что это неправильно по двум причинам: 1. Существует две версии псевдокода, и я не думаю, что они оба исправляются одновременно. 2. Я следовал заданному псевдокоду, и он не работает, я также следовал второму псевдокоду, и он тоже не работает. Итак, мой вопрос, есть ли в моей реализации ошибки по сравнению с псевдокодом? Я должен использовать given, но, очевидно, если это неправильно, мне нужно использовать правильный алгоритм

Ответ №1:

одна вещь, которую я заметил, это то, что swap должен получать индексы, и вы отправляете значения ячеек, которые хотите поменять местами:

 Swap(a, pos[m], pos[m]   d[m]);
Swap(pos, m, a[pos[m]]   d[m]);