Комбинаторика: Перестановки

1001

July 20, 2018

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

Например, вот перестановки чисел 1, 2, 3:

123, 132, 213, 231, 312, 321.

А что, если нам нужно найти все перестановки не чисел или букв, а объектов данных?

Для Java я нашел класс, который позволяет получить все перестановки.


    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() {

        }
    }

Использовать его можно так:

    String[] s = {"1", "2", "3"};

    Permutations<String> p = new Permutations<String>(s);
    while (p.hasNext()) {
        for (String a : p.next()) {
            System.out.print(a);
        }
        System.out.println();
    }

Вывод:

123
132
213
231
312
321