Советы по реализации алгоритма перестановок в Java

Ответ 1

Согласно совету Говарда, я решил, что не хочу использовать ничего, кроме примитивного типа массива. Первоначально выбранный алгоритм представлял собой боль для реализации на Java, поэтому, благодаря советам преследователей, я пошел с лексикографическим алгоритмом, описанным в Википедии. Вот что я закончил:

public static int[][] generatePermutations(int N) {
    int[][] a = new int[factorial(N)][N];
    for (int i = 0; i < N; i++) a[0][i] = i;
    for (int i = 1; i < a.length; i++) {
        a[i] = Arrays.copyOf(a[i-1], N);
        int k, l;
        for (k = N - 2; a[i][k] >= a[i][k+1]; k--);
        for (l = N - 1; a[i][k] >= a[i][l]; l--);
        swap(a[i], k, l);
        for (int j = 1; k+j < N-j; j++) swap(a[i], k+j, N-j);
    }
    return a;
}
private static void swap(int[] is, int k, int l) {
    int tmp_k = is[k];
    int tmp_l = is[l];
    is[k] = tmp_l;
    is[l] = tmp_k;
}

Ответ 2

Как вы знаете, количество перестановок заранее (это N!), а также вы хотите/должны вернуть int[][], я бы пошел на массив напрямую. Вы можете объявить его в начале с правильными размерами и вернуть его в конце. Таким образом, вам не нужно беспокоиться о том, чтобы преобразовать его впоследствии.

Ответ 3

Поскольку вы в значительной степени выполнили его самостоятельно в javascript, я продолжу и дам вам код Java для реализации алгоритма перестановки Steinhaus. Я просто портировал ваш код на Java, оставляя столько же, сколько мог, включая комментарии.

Я тестировал его до N = 7. Я попытался вычислить N = 8, но он работал почти 10 минут на процессоре Intel Core 2 Duo с частотой 2 ГГц и все еще идет, lol.

Я уверен, что если бы вы действительно работали над этим, вы могли бы значительно ускорить это, но даже тогда вы, вероятно, только сможете сжать, может быть, еще пару N-ценностей, если, конечно, у вас нет доступ к суперкомпьютеру; -).

Предупреждение - этот код верный, а не надежный. Если вам это нужно, то вы, как правило, не выполняете домашние задания, то это будет упражнение, оставленное вам. Я бы также рекомендовал реализовать его с помощью Java Collections просто потому, что это отличный способ изучить интерфейс API коллекций и из него.

В него включены несколько "вспомогательных" методов, в том числе один для печати массива 2d. Наслаждайтесь!

Обновление: N = 8 заняло 25 минут, 38 секунд.

Изменить: Исправлены N == 1 и N == 2.

public class Test
{
  public static void main (String[] args)
  {
    printArray (allPermutations (8));
  }

  public static int[][] allPermutations (int N)
  {
    // base case
    if (N == 2)
    {
      return new int[][] {{1, 2}, {2, 1}};
    }
    else if (N > 2)
    {
      // start with all permutations of previous degree
      int[][] permutations = allPermutations (N - 1);

      for (int i = 0; i < factorial (N); i += N)
      {
        // copy each permutation N - 1 times
        for (int j = 0; j < N - 1; ++j)
        {
          // similar to javascript array.splice
          permutations = insertRow (permutations, i, permutations [i]);
        }
      }

      // "weave" next number in
      for (int i = 0, j = N - 1, d = -1; i < permutations.length; ++i)
      {
        // insert number N at index j
        // similar to javascript array.splice
        permutations = insertColumn (permutations, i, j, N);

        // index j is  N-1, N-2, N-3, ... , 1, 0; then 0, 1, 2, ... N-1; then N-1, N-2, etc.
        j += d;

        // at beginning or end of the row, switch weave direction
        if (j < 0 || j > N - 1)
        {
          d *= -1;
          j += d;
        }
      }

      return permutations;
    }
    else
    {
      throw new IllegalArgumentException ("N must be >= 2");
    }
  }

  private static void arrayDeepCopy (int[][] src, int srcRow, int[][] dest,
                                     int destRow, int numOfRows)
  {
    for (int row = 0; row < numOfRows; ++row)
    {
      System.arraycopy (src [srcRow + row], 0, dest [destRow + row], 0,
                        src[row].length);
    }
  }

  public static int factorial (int n)
  {
    return n == 1 ? 1 : n * factorial (n - 1);
  }

  private static int[][] insertColumn (int[][] src, int rowIndex,
                                       int columnIndex, int columnValue)
  {
    int[][] dest = new int[src.length][0];

    for (int i = 0; i < dest.length; ++i)
    {
      dest [i] = new int [src[i].length];
    }

    arrayDeepCopy (src, 0, dest, 0, src.length);

    int numOfColumns = src[rowIndex].length;

    int[] rowWithExtraColumn = new int [numOfColumns + 1];

    System.arraycopy (src [rowIndex], 0, rowWithExtraColumn, 0, columnIndex);

    System.arraycopy (src [rowIndex], columnIndex, rowWithExtraColumn,
                      columnIndex + 1, numOfColumns - columnIndex);

    rowWithExtraColumn [columnIndex] = columnValue;

    dest [rowIndex] = rowWithExtraColumn;

    return dest;
  }

  private static int[][] insertRow (int[][] src, int rowIndex,
                                    int[] rowElements)
  {
    int srcRows = src.length;
    int srcCols = rowElements.length;

    int[][] dest = new int [srcRows + 1][srcCols];

    arrayDeepCopy (src, 0, dest, 0, rowIndex);
    arrayDeepCopy (src, rowIndex, dest, rowIndex + 1, src.length - rowIndex);

    System.arraycopy (rowElements, 0, dest [rowIndex], 0, rowElements.length);

    return dest;
  }

  public static void printArray (int[][] array)
  {
    for (int row = 0; row < array.length; ++row)
    {
      for (int col = 0; col < array[row].length; ++col)
      {
        System.out.print (array [row][col] + " ");
      }

      System.out.print ("\n");
    }

    System.out.print ("\n");
  }
}

Ответ 4

Ява-массивы не изменяются (в том смысле, вы не можете изменить их длину). Для прямого перевода этого рекурсивного алгоритма вы, вероятно, захотите использовать интерфейс List (и, возможно, реализацию LinkedList, поскольку вы хотите, чтобы номера были посередине). Это List<List<Integer>>.

Остерегайтесь факториала быстро возрастает: при N = 13 существует 13! перестановок 6 227 020 800. Но я думаю, вам нужно запустить его только для небольших значений.

Алгоритм выше довольно сложный, мое решение будет:

• создать List<int[]> для хранения всех перестановок
• создайте один массив размера N и заполните его идентификатором ({1,2,3,..., N})
• функция программы, которая на месте создает следующую перестановку в лексикографическом порядке
• повторите это, пока не получите идентификатор еще раз:
  • поместите копию массива в конец списка
  • вызов метода для получения следующей перестановки.

Если вашей программе просто нужно вывести все перестановки, я бы избегал их хранить и сразу печатать.

Алгоритм вычисления следующей перестановки можно найти в Интернете. Здесь, например,

Ответ 5

Используйте все, что хотите, массивы или списки, но не конвертируйте их - это просто усложняет работу. Я не могу сказать, что лучше, возможно, я бы пошел на ArrayList<int[]>, так как внешний список позволяет мне легко добавить перестановку, а внутренний массив достаточно хорош. Это просто вопрос вкуса (но обычно предпочитают списки, поскольку они намного более гибкие).