Перестановка блока


у меня есть этот массив:

int a[] = new int[]{3,4,6,2,1};

мне нужен список всех перестановок таких, что если один такой, {3,2,1,4,6}, другие люди не должны быть одинаковыми. Я знаю, что если длина массива n здесь n! возможных комбинаций. Как можно написать этот алгоритм?

Update: спасибо, но мне нужен алгоритм псевдо-кода, например:

for(int i=0;i<a.length;i++){
    // code here
}

просто алгоритм. Да, функции API хороши, но мне это тоже не помогает много.

9 53

9 ответов:

Если вы используете 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));

вот как вы можете напечатать все перестановки в 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;
    }
}

вот полный код итератора. Конструктор принимает массив объектов и отображает их в массив целых чисел, используя 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 перестановок.

вот реализация перестановки в Java:

Перестановка-Java

вы должны проверить это!

изменить: код вставлен ниже, чтобы защитить от link-death:

// 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);
      }
   }
}

Это 2-перестановка для списка, завернутого в итератор

import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;

/* all permutations of two objects 
 * 
 * for ABC: AB AC BA BC CA CB
 * 
 * */
public class ListPermutation<T> implements Iterator {

    int index = 0;
    int current = 0;
    List<T> list;

    public ListPermutation(List<T> e) {
        list = e;
    }

    public boolean hasNext() {
        return !(index == list.size() - 1 && current == list.size() - 1);
    }

    public List<T> next() {
        if(current == index) {
            current++;
        }
        if (current == list.size()) {
            current = 0;
            index++;
        }
        List<T> output = new LinkedList<T>();
        output.add(list.get(index));
        output.add(list.get(current));
        current++;
        return output;
    }

    public void remove() {
    }

}

здесь n! всего перестановок для данного размера массива n. Вот код, написанный на Java с помощью DFS.

public List<List<Integer>> permute(int[] nums) {
    List<List<Integer>> results = new ArrayList<List<Integer>>();
    if (nums == null || nums.length == 0) {
        return results;
    }
    List<Integer> result = new ArrayList<>();
    dfs(nums, results, result);
    return results;
}

public void dfs(int[] nums, List<List<Integer>> results, List<Integer> result) {
    if (nums.length == result.size()) {
        List<Integer> temp = new ArrayList<>(result);
        results.add(temp);
    }        
    for (int i=0; i<nums.length; i++) {
        if (!result.contains(nums[i])) {
            result.add(nums[i]);
            dfs(nums, results, result);
            result.remove(result.size() - 1);
        }
    }
}

для входного массива [3,2,1,4,6], есть полностью 5! = 120 возможных перестановок, которые являются:

[[3,4,6,2,1],[3,4,6,1,2],[3,4,2,6,1],[3,4,2,1,6],[3,4,1,6,2],[3,4,1,2,6],[3,6,4,2,1],[3,6,4,1,2],[3,6,2,4,1],[3,6,2,1,4],[3,6,1,4,2],[3,6,1,2,4],[3,2,4,6,1],[3,2,4,1,6],[3,2,6,4,1],[3,2,6,1,4],[3,2,1,4,6],[3,2,1,6,4],[3,1,4,6,2],[3,1,4,2,6],[3,1,6,4,2],[3,1,6,2,4],[3,1,2,4,6],[3,1,2,6,4],[4,3,6,2,1],[4,3,6,1,2],[4,3,2,6,1],[4,3,2,1,6],[4,3,1,6,2],[4,3,1,2,6],[4,6,3,2,1],[4,6,3,1,2],[4,6,2,3,1],[4,6,2,1,3],[4,6,1,3,2],[4,6,1,2,3],[4,2,3,6,1],[4,2,3,1,6],[4,2,6,3,1],[4,2,6,1,3],[4,2,1,3,6],[4,2,1,6,3],[4,1,3,6,2],[4,1,3,2,6],[4,1,6,3,2],[4,1,6,2,3],[4,1,2,3,6],[4,1,2,6,3],[6,3,4,2,1],[6,3,4,1,2],[6,3,2,4,1],[6,3,2,1,4],[6,3,1,4,2],[6,3,1,2,4],[6,4,3,2,1],[6,4,3,1,2],[6,4,2,3,1],[6,4,2,1,3],[6,4,1,3,2],[6,4,1,2,3],[6,2,3,4,1],[6,2,3,1,4],[6,2,4,3,1],[6,2,4,1,3],[6,2,1,3,4],[6,2,1,4,3],[6,1,3,4,2],[6,1,3,2,4],[6,1,4,3,2],[6,1,4,2,3],[6,1,2,3,4],[6,1,2,4,3],[2,3,4,6,1],[2,3,4,1,6],[2,3,6,4,1],[2,3,6,1,4],[2,3,1,4,6],[2,3,1,6,4],[2,4,3,6,1],[2,4,3,1,6],[2,4,6,3,1],[2,4,6,1,3],[2,4,1,3,6],[2,4,1,6,3],[2,6,3,4,1],[2,6,3,1,4],[2,6,4,3,1],[2,6,4,1,3],[2,6,1,3,4],[2,6,1,4,3],[2,1,3,4,6],[2,1,3,6,4],[2,1,4,3,6],[2,1,4,6,3],[2,1,6,3,4],[2,1,6,4,3],[1,3,4,6,2],[1,3,4,2,6],[1,3,6,4,2],[1,3,6,2,4],[1,3,2,4,6],[1,3,2,6,4],[1,4,3,6,2],[1,4,3,2,6],[1,4,6,3,2],[1,4,6,2,3],[1,4,2,3,6],[1,4,2,6,3],[1,6,3,4,2],[1,6,3,2,4],[1,6,4,3,2],[1,6,4,2,3],[1,6,2,3,4],[1,6,2,4,3],[1,2,3,4,6],[1,2,3,6,4],[1,2,4,3,6],[1,2,4,6,3],[1,2,6,3,4],[1,2,6,4,3]]

надеюсь, что это помогает.

пример с примитивным массивом:

public static void permute(int[] intArray, int start) {
    for(int i = start; i < intArray.length; i++){
        int temp = intArray[start];
        intArray[start] = intArray[i];
        intArray[i] = temp;
        permute(intArray, start + 1);
        intArray[i] = intArray[start];
        intArray[start] = temp;
    }
    if (start == intArray.length - 1) {
        System.out.println(java.util.Arrays.toString(intArray));
    }
}

public static void main(String[] args){
    int intArr[] = {1, 2, 3};
    permute(intArr, 0);
}

визуальное представление рекурсивного решения из 3 элементов: http://www.docdroid.net/ea0s/generatepermutations.pdf.html

поломки:

  1. для массива из двух элементов существует две перестановки:
    • исходный массив, и
    • два элемента меняются местами
  2. для массива из трех элементов существует шесть перестановок:
    • перестановки нижних двух элементов, тогда
    • поменять местами 1-й и 2-й элементы, а также перестановки двух нижних элементов
    • поменять местами 1-й и 3-й элементы, а также перестановки нижних двух элементов.
    • по сути, каждый из элементов получает свой шанс в первом слоте

простая реализация java, см. c++ std::next_permutation:

public static void main(String[] args){
    int[] list = {1,2,3,4,5};
    List<List<Integer>> output = new Main().permute(list);
    for(List result: output){
        System.out.println(result);
    }

}

public List<List<Integer>> permute(int[] nums) {
    List<List<Integer>> list = new ArrayList<List<Integer>>();
    int size = factorial(nums.length);

    // add the original one to the list
    List<Integer> seq = new ArrayList<Integer>();
    for(int a:nums){
        seq.add(a);
    }
    list.add(seq);

    // generate the next and next permutation and add them to list
    for(int i = 0;i < size - 1;i++){
        seq = new ArrayList<Integer>();
        nextPermutation(nums);
        for(int a:nums){
            seq.add(a);
        }
        list.add(seq);
    }
    return list;
}


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

void nextPermutation(int[] nums){
    int i = nums.length -1; // start from the end

    while(i > 0 && nums[i-1] >= nums[i]){
        i--;
    }

    if(i==0){
        reverse(nums,0,nums.length -1 );
    }else{

        // found the first one not in order 
        int j = i;

        // found just bigger one
        while(j < nums.length && nums[j] > nums[i-1]){
            j++;
        }
        //swap(nums[i-1],nums[j-1]);
        int tmp = nums[i-1];
        nums[i-1] = nums[j-1];
        nums[j-1] = tmp;
        reverse(nums,i,nums.length-1);  
    }
}

// reverse the sequence
void reverse(int[] arr,int start, int end){
    int tmp;
    for(int i = 0; i <= (end - start)/2; i++ ){
        tmp = arr[start + i];
        arr[start + i] = arr[end - i];
        arr[end - i ] = tmp;
    }
}

сделайте так...

import java.util.ArrayList;
import java.util.Arrays;

public class rohit {

    public static void main(String[] args) {
        ArrayList<Integer> a=new ArrayList<Integer>();
        ArrayList<Integer> b=new ArrayList<Integer>();
        b.add(1);
        b.add(2);
        b.add(3);
        permu(a,b);
    }

    public static void permu(ArrayList<Integer> prefix,ArrayList<Integer> value) {
        if(value.size()==0) {
            System.out.println(prefix);
        } else {
            for(int i=0;i<value.size();i++) {
                ArrayList<Integer> a=new ArrayList<Integer>();
                a.addAll(prefix);
                a.add(value.get(i));

                ArrayList<Integer> b=new ArrayList<Integer>();

                b.addAll(value.subList(0, i));
                b.addAll(value.subList(i+1, value.size()));

                permu(a,b);
            }
        }
    }

}