Алгоритм перестановки без рекурсии? Джава

Question

Алгоритм перестановки без рекурсии? Джава

Если вы хотите, чтобы записи данных набора данных были сообщены на странице , это нужно было бы сделать с помощью кросс-таблицы.

Если вы хотите, чтобы записи о наборах данных указывались вниз страницы, это невозможно сделать автоматически, насколько я знаю. Однако это можно сделать, вставив новую строку подробностей в объект таблицы отчетов для каждого поля базы данных, которое должно быть сообщено, а затем перемещение заголовков столбцов из строки заголовка в строки подробностей первого столбца и перемещение значений записи во строки подробных данных второго столбца.

Итак, например, отчет с шестью столбцами в нем станет двухстолбцовым отчетом с шестью строчными строками.

37

permutation sequence recursion java

задан dckrooney 2 May 2012 в 06:54

2 ответа

Другие вопросы по тегам:

permutation sequence recursion java

Похожие вопросы:

score 8 · Answer 1

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

Для этой конкретной проблемы может быть более поучительным взглянуть на алгоритм C ++ STL std :: next_permutation . Согласно Томасу Гесту с wordaligned.org , базовая реализация выглядит следующим образом:

template<typename Iter>
bool next_permutation(Iter first, Iter last)
{
    if (first == last)
        return false;
    Iter i = first;
    ++i;
    if (i == last)
        return false;
    i = last;
    --i;

    for(;;)
    {
        Iter ii = i;
        --i;
        if (*i < *ii)
        {
            Iter j = last;
            while (!(*i < *--j))
            {}
            std::iter_swap(i, j);
            std::reverse(ii, last);
            return true;
        }
        if (i == first)
        {
            std::reverse(first, last);
            return false;
        }
    }
}

Обратите внимание, что она не использует рекурсию и относительно просто переводится на другой C-подобный язык, такой как Java.Вы можете прочитать о std :: iter_swap , std :: reverse и двунаправленных итераторах (что представляет собой Iter в этом код).

score 17 · Answer 2

Вот общий перечислитель перестановок, который я написал год назад. Он также может создавать "подперестановки":

public class PermUtil <T> {
 private T[] arr;
 private int[] permSwappings;

 public PermUtil(T[] arr) {
  this(arr,arr.length);
 }

 public PermUtil(T[] arr, int permSize) {
  this.arr = arr.clone();
  this.permSwappings = new int[permSize];
  for(int i = 0;i < permSwappings.length;i++)
   permSwappings[i] = i;
 }

 public T[] next() {
  if (arr == null)
   return null;

  T[] res = Arrays.copyOf(arr, permSwappings.length);
  //Prepare next
  int i = permSwappings.length-1;
  while (i >= 0 && permSwappings[i] == arr.length - 1) {
   swap(i, permSwappings[i]); //Undo the swap represented by permSwappings[i]
   permSwappings[i] = i;
   i--;
  }

  if (i < 0)
   arr = null;
  else {   
   int prev = permSwappings[i];
   swap(i, prev);
   int next = prev + 1;
   permSwappings[i] = next;
   swap(i, next);
  }

  return res;
 }

 private void swap(int i, int j) {
  T tmp = arr[i];
  arr[i] = arr[j];
  arr[j] = tmp;
 }

}

Идея моего алгоритма в том, что любую перестановку можно выразить как уникальную последовательность команд подкачки. Например, для последовательность обмена 012 оставляет все элементы на месте, а 122 начинается с замены индекса 0 на индекс 1, затем меняет 1 на 2, а затем меняет 2 на 2 (т.е. оставляет их на месте). В результате получается перестановка BCA.

Это представление изоморфно представлению перестановок (т.е. отношение один к одному), и его очень легко "увеличить" при обходе пространства перестановок. Для 4 элементов оно начинается с 0123 (ABCD) и заканчивается 3333 (DABC).