Сложная проблема генерации перестановки Java - PullRequest
Новая
       5

Сложная проблема генерации перестановки Java

2 голосов
/ 02 апреля 2011

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

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

Конкретным примером является массив int, называемый условиями со следующими данными: 

conditions1 = {1,2,3,4}
conditions2 = {1,2,3}
conditions3 = {1,2,3}
conditions4 = {1,2}
conditions5 = {1,2}

, и я хочу создать таблицу из 5 столбцов всех возможных перестановок - в этом случае 144 (4x3x3x2x2),Столбец 1 может использовать только значения из условий 1 и столбец 2 из условий 2 и т. Д.

Вывод будет: 

1,1,1,1,1
1,1,1,1,2
1,1,1,2,1
1,1,1,2,2
1,1,2,1,1
.
.
through to 
4,3,3,2,2

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

Буду признателен за любую помощь.

Z.

1 Ответ

1 голос
/ 02 апреля 2011

Смотри, ма, рекурсия не нужна. 

Iterator<int[]> permutations(final int[]... conditions) {
  int productLengths = 1;
  for (int[] arr : conditions) { productLengths *= arr.length; }
  final int nPermutations = productLengths;
  return new Iterator<int[]>() {
    int index = 0;
    public boolean hasNext() { return index < nPermutations; }
    public int[] next() {
      if (index == nPermutations) { throw new NoSuchElementException(); }
      int[] out = new int[conditions.length];
      for (int i = out.length, x = index; --i >= 0;) {
        int[] arr = conditions[i];
        out[i] = arr[x % arr.length];
        x /= arr.length;
      }
      ++index;
      return out;
    }
    public void remove() { throw new UnsupportedOperationException(); }
  };
}

Завершение в Iterable<int[]> облегчит использование с for (... : ...) петлей. Вы можете избавиться от распределения массива, покончив с интерфейсом итератора и просто взяв в качестве аргумента массив для заполнения.

...