Java все перестановки элементов массива

напечатать все возможные перестановки элементов r в заданном целочисленном массиве размера n в Java

Учитывая массив размера n, сгенерируйте и распечатайте все возможные перестановки элементов r в массиве.

Например, если n равно 4, входной массив равен [0, 1, 2, 3], а r равно 3, тогда выход должен быть равен

[0, 1, 2] [0, 1, 3] [0, 2, 1] [0, 2, 3] [0, 3, 1] [0, 3, 2] [1, 0, 2] [1, 0, 3] [1, 2, 0] [1, 2, 3] [1, 3, 0] [1, 3, 2] [2, 0, 1] [2, 0, 3] [2, 1, 0] [2, 1, 3] [2, 3, 0] [2, 3, 1] [3, 0, 1] [3, 0, 2] [3, 1, 0] [3, 1, 2] [3, 2, 0] [3, 2, 1] 

Все элементы во входном массиве являются целыми числами, от 0 до n-1. Как я могу использовать Java для печати всех возможных перестановок?

Важно: количество всех элементов в одной перестановке – это не всегда размер исходного массива. Это меньше или равно размеру исходного массива. Кроме того, порядок элементов в каждой перестановке имеет значение.

Я написал код при n = 4 и r = 3. Если n = 100 и r = 50, мой код будет действительно уродливым. Есть ли разумный способ сделать это, когда параметры являются только n и r?

public static void main(String[] args) < // original array ArrayList < Integer >items = new ArrayList < >(); // all permutations ArrayList < ArrayList < Integer >> allPermutations = new ArrayList < ArrayList < Integer >> (); // define the end item of the original array. // this is n, suppose it 4 now. int endItem = 4; for (int i = 0; i < endItem; i++) < items.add(i); >// r means how many elements in each single permutation // suppose it 3 now, i have to write for-loop three times // if r is 100, i have to write for-loop 100 times // first of the "r" for (int i = 0; i < items.size(); i++) < // second of the "r" for (int j = 0; j < items.size(); j++) < // can't be identical to i if (j == i) continue; // third of the "r" for (int k = 0; k < items.size(); k++) < // can't be identical to i or j if (k == i || k == j) continue; // a single permutation ArrayList < Integer >singlePermutation = new ArrayList < >(); singlePermutation.add(items.get(i)); singlePermutation.add(items.get(j)); singlePermutation.add(items.get(k)); // all permutations allPermutations.add(singlePermutation); > > > for (ArrayList < Integer >permutation: allPermutations) < System.out.println(permutation); >System.out.println(allPermutations.size()); > 

Перемещено решение из вопроса, чтобы ответить:

Решение:

Благодаря старшему кодеру мне удалось найти решение.

public class PermutationTest10 < // a is the original array // k is the number of elements in each permutation public static ArrayList> choose(ArrayList a, int k) < ArrayList> allPermutations = new ArrayList>(); enumerate(a, a.size(), k, allPermutations); return allPermutations; > // a is the original array // n is the array size // k is the number of elements in each permutation // allPermutations is all different permutations private static void enumerate(ArrayList a, int n, int k, ArrayList> allPermutations) < if (k == 0) < ArrayListsinglePermutation = new ArrayList(); for (int i = n; i < a.size(); i++)< singlePermutation.add(a.get(i)); >allPermutations.add(singlePermutation); return; > for (int i = 0; i < n; i++) < swap(a, i, n-1); enumerate(a, n-1, k-1, allPermutations); swap(a, i, n-1); >> // helper function that swaps a.get(i) and a.get(j) public static void swap(ArrayList a, int i, int j) < Integer temp = a.get(i); a.set(i, a.get(j)); a.set(j, temp); >// sample client public static void main(String[] args) < // n is the end item of the array. // if n = 5, the array is [0, 1, 2, 3, 4, 5] // k is the number of elements of each permutation. int n =5; int k =3; // create original array ArrayListelements = new ArrayList<> (); for (int i =0; i < n; i ++)< elements.add(i); >ArrayList a = new ArrayList<> (); for (int i = 0; i < n; i ++)< a.add(elements.get(i)); >System.out.println(choose(a, k)); > > 

Источник

Перестановки массива в Java

Краткое и практическое руководство по созданию перестановок массивов на Java.

1. введение

В этой статье мы рассмотрим, как создавать перестановки массива .

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

Мы сосредоточимся на реализации на Java и поэтому не будем вдаваться в математические подробности.

2. Что такое Перестановка?

Перестановка множества – это перестановка его элементов. Набор, состоящий из n элементов, имеет n! перестановки. Здесь н! – это факториал, который является произведением всех положительных целых чисел, меньших или равных n .

2.1. Пример

Массив целых чисел [3,4,7] состоит из трех элементов и шести перестановок:

Перестановки: [3,4,7]; [3,7,4]; [4,7,3]; [4,3,7]; [7,3,4]; [7,4,3]

2.2. Ограничения

Число перестановок быстро увеличивается с n . Хотя для создания всех перестановок из десяти элементов требуется всего несколько секунд, для создания всех перестановок из 15 элементов потребуется две недели:

3. Алгоритмы

3.1. Рекурсивный алгоритм

Первый алгоритм, который мы рассмотрим, это Алгоритм кучи . Это рекурсивный алгоритм, который производит все перестановки путем замены одного элемента на итерацию.

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

public static void printAllRecursive( int n, T[] elements, char delimiter) < if(n == 1) < printArray(elements, delimiter); >else < for(int i = 0; i < n-1; i++) < printAllRecursive(n - 1, elements, delimiter); if(n % 2 == 0) < swap(elements, i, n-1); >else < swap(elements, 0, n-1); >> printAllRecursive(n - 1, elements, delimiter); > > 

Метод использует два вспомогательных метода:

private void swap(T[] input, int a, int b)

private void printArray(T[] input) < System.out.print('\n'); for(int i = 0; i < input.length; i++) < System.out.print(input[i]); >>

Здесь мы записываем результат в System.out , однако вместо этого мы можем легко сохранить результат в массиве или в списке.

3.2. Итерационный алгоритм

Алгоритм кучи также может быть реализован с помощью итераций:

int[] indexes = new int[n]; int[] indexes = new int[n]; for (int i = 0; i < n; i++) < indexes[i] = 0; >printArray(elements, delimiter); int i = 0; while (i < n) < if (indexes[i] < i) < swap(elements, i % 2 == 0 ? 0: indexes[i], i); printArray(elements, delimiter); indexes[i]++; i = 0; >else < indexes[i] = 0; i++; >>

3.3. Перестановки в лексикографическом порядке

Если элементы сопоставимы, мы можем генерировать перестановки, отсортированные по естественному порядку элементов:

public static > void printAllOrdered( T[] elements, char delimiter) < Arrays.sort(elements); boolean hasNext = true; while(hasNext) < printArray(elements, delimiter); int k = 0, l = 0; hasNext = false; for (int i = elements.length - 1; i >0; i--) < if (elements[i].compareTo(elements[i - 1]) >0) < k = i - 1; hasNext = true; break; >> for (int i = elements.length - 1; i > k; i--) < if (elements[i].compareTo(elements[k]) >0) < l = i; break; >> swap(elements, k, l); Collections.reverse(Arrays.asList(elements).subList(k + 1, elements.length)); > > 

Этот алгоритм имеет обратную операцию на каждой итерации, и поэтому он менее эффективен для массивов, чем алгоритм Кучи.

3.4. Рандомизированный алгоритм

Если n велико, мы можем сгенерировать случайную перестановку путем перетасовки массива:

Collections.shuffle(Arrays.asList(elements));

Мы можем сделать это несколько раз, чтобы сгенерировать выборку перестановок.

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

4. Заключение

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

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

Реализацию всех фрагментов кода в этой статье можно найти в нашем репозитории Github .

Читайте ещё по теме:

Источник

Перестановки массива в Java

Мы сосредоточимся на реализации на Java и поэтому не будем вдаваться в математические подробности.

2. Что такое перестановка?​

Перестановка множества — это перестановка его элементов. Множество, состоящее из n элементов, имеет n! перестановки. Вот н! является факториалом, который является произведением всех положительных целых чисел, меньших или равных n .

2.1. Пример​

Массив целых чисел [3,4,7] состоит из трех элементов и шести перестановок:

Перестановки: [3,4,7] ; [3,7,4] ; [4,7,3] ; [4,3,7] ; [7,3,4] ; [7,4,3]

2.2. Ограничения​

Число перестановок быстро увеличивается с n . Хотя для генерации всех перестановок из десяти элементов требуется всего несколько секунд, для генерации всех перестановок из 15 элементов потребуется две недели:

3. Алгоритмы​

3.1. Рекурсивный алгоритм​

Первый алгоритм, который мы рассмотрим, — это алгоритм Хипа . Это рекурсивный алгоритм, который производит все перестановки, заменяя один элемент за итерацию.

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

 public static T> void printAllRecursive(   int n, T[] elements, char delimiter)     if(n == 1)    printArray(elements, delimiter);   > else    for(int i = 0; i  n-1; i++)    printAllRecursive(n - 1, elements, delimiter);   if(n % 2 == 0)    swap(elements, i, n-1);   > else    swap(elements, 0, n-1);   >   >   printAllRecursive(n - 1, elements, delimiter);   >   > 

Метод использует два вспомогательных метода:

 private void swap(T[] input, int a, int b)    T tmp = input[a];   input[a] = input[b];   input[b] = tmp;   > 

 private void printArray(T[] input)    System.out.print('\n');   for(int i = 0; i  input.length; i++)    System.out.print(input[i]);   >   > 

Здесь мы записываем результат в System.out , однако вместо этого мы можем легко сохранить результат в массиве или в списке.

3.2. Итеративный алгоритм​

Алгоритм кучи также можно реализовать с помощью итераций:

 int[] indexes = new int[n];   int[] indexes = new int[n];   for (int i = 0; i  n; i++)    indexes[i] = 0;   >    printArray(elements, delimiter);    int i = 0;   while (i  n)    if (indexes[i]  i)    swap(elements, i % 2 == 0 ? 0: indexes[i], i);   printArray(elements, delimiter);   indexes[i]++;   i = 0;   >   else    indexes[i] = 0;   i++;   >   > 

3.3. Перестановки в лексикографическом порядке​

Если элементы сопоставимы, мы можем генерировать перестановки, отсортированные по естественному порядку элементов:

 public static T extends ComparableT>> void printAllOrdered(   T[] elements, char delimiter)     Arrays.sort(elements);   boolean hasNext = true;    while(hasNext)    printArray(elements, delimiter);   int k = 0, l = 0;   hasNext = false;   for (int i = elements.length - 1; i > 0; i--)    if (elements[i].compareTo(elements[i - 1]) > 0)    k = i - 1;   hasNext = true;   break;   >   >    for (int i = elements.length - 1; i > k; i--)    if (elements[i].compareTo(elements[k]) > 0)    l = i;   break;   >   >    swap(elements, k, l);   Collections.reverse(Arrays.asList(elements).subList(k + 1, elements.length));   >   > 

Этот алгоритм имеет обратную операцию на каждой итерации и поэтому менее эффективен для массивов, чем алгоритм Heap.

3.4. Рандомизированный алгоритм​

Если n велико, мы можем сгенерировать случайную перестановку , перетасовав массив:

 Collections.shuffle(Arrays.asList(elements)); 

Мы можем сделать это несколько раз, чтобы сгенерировать выборку перестановок.

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

4. Вывод​

Есть много способов сгенерировать все перестановки массива. В этой статье мы увидели рекурсивный и итеративный алгоритм кучи и то, как создать отсортированный список перестановок.

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

Реализацию всех фрагментов кода в этой статье можно найти в нашем репозитории Github .

Источник