Перестановка массива
Например, у меня есть этот массив:
int a[] = new int[]{3,4,6,2,1};
Мне нужен список всех перестановок таким образом, чтобы, если одна из них была такой, {3,2,1,4,6} другие не должны совпадать. Я знаю, что если длина массива равна n, то существует n! возможных комбинаций. Как можно написать этот алгоритм?
Обновление: спасибо, но мне нужен алгоритм псевдокода типа:
for(int i=0;i<a.length;i++){
// code here
}
Просто алгоритм. Да, функции API хороши, но мне это не слишком помогает.
Переведено автоматически
Ответ 1
Вот как вы можете напечатать все перестановки в 10 строках кода:
public class Permute{
static void permute(java.util.List<Integer> arr, int k){
for(int i = k; i < arr.size(); i++){
java.util.Collections.swap(arr, i, k);
permute(arr, k+1);
java.util.Collections.swap(arr, k, i);
}
if (k == arr.size() -1){
System.out.println(java.util.Arrays.toString(arr.toArray()));
}
}
public static void main(String[] args){
Permute.permute(java.util.Arrays.asList(3,4,6,2,1), 0);
}
}
Вы берете первый элемент массива (k = 0) и заменяете его любым элементом (i) массива. Затем вы рекурсивно применяете перестановку к массиву, начиная со второго элемента. Таким образом, вы получите все перестановки, начинающиеся с i-го элемента. Сложность заключается в том, что после рекурсивного вызова вы должны поменять местами i-й элемент с первым элементом обратно, иначе вы могли бы получить повторяющиеся значения в первом месте. Меняя его местами, мы восстанавливаем порядок элементов (в основном вы выполняете обратный поиск).
Итераторы и расширение на случай повторяющихся значений
Недостатком предыдущего алгоритма является то, что он рекурсивен и плохо работает с итераторами. Другая проблема заключается в том, что если вы разрешаете повторяющиеся элементы во входных данных, то он не будет работать как есть.
Например, при заданных входных данных [3,3,4,4] все возможные перестановки (без повторений) являются
[3, 3, 4, 4]
[3, 4, 3, 4]
[3, 4, 4, 3]
[4, 3, 3, 4]
[4, 3, 4, 3]
[4, 4, 3, 3]
(если вы просто примените permute функцию сверху, вы получите [3,3,4,4] четыре раза, и это не то, что вы, естественно, хотите видеть в данном случае; и количество таких перестановок равно 4!/(2!*2!)=6)
Можно модифицировать приведенный выше алгоритм для обработки этого случая, но это будет выглядеть некрасиво. К счастью, есть алгоритм получше (я нашел его здесь), который обрабатывает повторяющиеся значения и не является рекурсивным.
Во-первых, обратите внимание, что перестановка массива любых объектов может быть сведена к перестановкам целых чисел путем перечисления их в любом порядке.
Чтобы получить перестановки массива целых чисел, вы начинаете с массива, отсортированного в порядке возрастания. Ваша "цель" - сделать его убывающим. Чтобы сгенерировать следующую перестановку, вы пытаетесь найти первый индекс снизу, где последовательность не является убывающей, и улучшаете значение в этом индексе, переключая порядок остальной части хвоста с убывающего на возрастающий в этом случае.
Вот суть алгоритма:
//ind is an array of integers
for(int tail = ind.length - 1;tail > 0;tail--){
if (ind[tail - 1] < ind[tail]){//still increasing
//find last element which does not exceed ind[tail-1]
int s = ind.length - 1;
while(ind[tail-1] >= ind[s])
s--;
swap(ind, tail-1, s);
//reverse order of elements in the tail
for(int i = tail, j = ind.length - 1; i < j; i++, j--){
swap(ind, i, j);
}
break;
}
}
Вот полный код iterator . Конструктор принимает массив объектов и преобразует их в массив целых чисел с помощью HashMap.
import java.lang.reflect.Array;
import java.util.*;
class Permutations<E> implements Iterator<E[]>{
private E[] arr;
private int[] ind;
private boolean has_next;
public E[] output;//next() returns this array, make it public
Permutations(E[] arr){
this.arr = arr.clone();
ind = new int[arr.length];
//convert an array of any elements into array of integers - first occurrence is used to enumerate
Map<E, Integer> hm = new HashMap<E, Integer>();
for(int i = 0; i < arr.length; i++){
Integer n = hm.get(arr[i]);
if (n == null){
hm.put(arr[i], i);
n = i;
}
ind[i] = n.intValue();
}
Arrays.sort(ind);//start with ascending sequence of integers
//output = new E[arr.length]; <-- cannot do in Java with generics, so use reflection
output = (E[]) Array.newInstance(arr.getClass().getComponentType(), arr.length);
has_next = true;
}
public boolean hasNext() {
return has_next;
}
/**
* Computes next permutations. Same array instance is returned every time!
* @return
*/
public E[] next() {
if (!has_next)
throw new NoSuchElementException();
for(int i = 0; i < ind.length; i++){
output[i] = arr[ind[i]];
}
//get next permutation
has_next = false;
for(int tail = ind.length - 1;tail > 0;tail--){
if (ind[tail - 1] < ind[tail]){//still increasing
//find last element which does not exceed ind[tail-1]
int s = ind.length - 1;
while(ind[tail-1] >= ind[s])
s--;
swap(ind, tail-1, s);
//reverse order of elements in the tail
for(int i = tail, j = ind.length - 1; i < j; i++, j--){
swap(ind, i, j);
}
has_next = true;
break;
}
}
return output;
}
private void swap(int[] arr, int i, int j){
int t = arr[i];
arr[i] = arr[j];
arr[j] = t;
}
public void remove() {
}
}
Использование / тест:
TCMath.Permutations<Integer> perm = new TCMath.Permutations<Integer>(new Integer[]{3,3,4,4,4,5,5});
int count = 0;
while(perm.hasNext()){
System.out.println(Arrays.toString(perm.next()));
count++;
}
System.out.println("total: " + count);
Выводит все 7!/(2!*3!*2!)=210 перестановки.
Ответ 2
Если вы используете C ++, вы можете использовать std::next_permutation из <algorithm> заголовочного файла:
int a[] = {3,4,6,2,1};
int size = sizeof(a)/sizeof(a[0]);
std::sort(a, a+size);
do {
// print a's elements
} while(std::next_permutation(a, a+size));
Ответ 3
Вот реализация перестановки в Java:
Вы должны это проверить!
Редактировать: код вставлен ниже для защиты от потери связи:
// Permute.java -- A class generating all permutations
import java.util.Iterator;
import java.util.NoSuchElementException;
import java.lang.reflect.Array;
public class Permute implements Iterator {
private final int size;
private final Object [] elements; // copy of original 0 .. size-1
private final Object ar; // array for output, 0 .. size-1
private final int [] permutation; // perm of nums 1..size, perm[0]=0
private boolean next = true;
// int[], double[] array won't work :-(
public Permute (Object [] e) {
size = e.length;
elements = new Object [size]; // not suitable for primitives
System.arraycopy (e, 0, elements, 0, size);
ar = Array.newInstance (e.getClass().getComponentType(), size);
System.arraycopy (e, 0, ar, 0, size);
permutation = new int [size+1];
for (int i=0; i<size+1; i++) {
permutation [i]=i;
}
}
private void formNextPermutation () {
for (int i=0; i<size; i++) {
// i+1 because perm[0] always = 0
// perm[]-1 because the numbers 1..size are being permuted
Array.set (ar, i, elements[permutation[i+1]-1]);
}
}
public boolean hasNext() {
return next;
}
public void remove() throws UnsupportedOperationException {
throw new UnsupportedOperationException();
}
private void swap (final int i, final int j) {
final int x = permutation[i];
permutation[i] = permutation [j];
permutation[j] = x;
}
// does not throw NoSuchElement; it wraps around!
public Object next() throws NoSuchElementException {
formNextPermutation (); // copy original elements
int i = size-1;
while (permutation[i]>permutation[i+1]) i--;
if (i==0) {
next = false;
for (int j=0; j<size+1; j++) {
permutation [j]=j;
}
return ar;
}
int j = size;
while (permutation[i]>permutation[j]) j--;
swap (i,j);
int r = size;
int s = i+1;
while (r>s) { swap(r,s); r--; s++; }
return ar;
}
public String toString () {
final int n = Array.getLength(ar);
final StringBuffer sb = new StringBuffer ("[");
for (int j=0; j<n; j++) {
sb.append (Array.get(ar,j).toString());
if (j<n-1) sb.append (",");
}
sb.append("]");
return new String (sb);
}
public static void main (String [] args) {
for (Iterator i = new Permute(args); i.hasNext(); ) {
final String [] a = (String []) i.next();
System.out.println (i);
}
}
}
Ответ 4
Согласно wiki https://en.wikipedia.org/wiki/Heap%27s_algorithm
Алгоритм Heap генерирует все возможные перестановки n объектов. Впервые он был предложен Б. Р. Хипом в 1963 году. Алгоритм минимизирует перемещение: он генерирует каждую перестановку из предыдущей путем замены одной пары элементов; остальные n−2 элемента не нарушаются. В обзоре алгоритмов генерации перестановок 1977 года Роберт Седжвик пришел к выводу, что на тот момент это был наиболее эффективный алгоритм для генерации перестановок компьютером.
Итак, если мы хотим сделать это рекурсивным способом, ниже приведен код Sudo.
procedure generate(n : integer, A : array of any):
if n = 1 then
output(A)
else
for i := 0; i < n - 1; i += 1 do
generate(n - 1, A)
if n is even then
swap(A[i], A[n-1])
else
swap(A[0], A[n-1])
end if
end for
generate(n - 1, A)
end if
java-код:
public static void printAllPermutations(
int n, int[] elements, char delimiter) {
if (n == 1) {
printArray(elements, delimiter);
} else {
for (int i = 0; i < n - 1; i++) {
printAllPermutations(n - 1, elements, delimiter);
if (n % 2 == 0) {
swap(elements, i, n - 1);
} else {
swap(elements, 0, n - 1);
}
}
printAllPermutations(n - 1, elements, delimiter);
}
}
private static void printArray(int[] input, char delimiter) {
int i = 0;
for (; i < input.length; i++) {
System.out.print(input[i]);
}
System.out.print(delimiter);
}
private static void swap(int[] input, int a, int b) {
int tmp = input[a];
input[a] = input[b];
input[b] = tmp;
}
public static void main(String[] args) {
int[] input = new int[]{0,1,2,3};
printAllPermutations(input.length, input, ',');
}