Интересная проблема сортировки

Думаю, это должно сработать:

• Повторите один раз, чтобы найти позицию Соединенные штаты. Если они не займут последние два места, переместите их туда поменять местами с двумя последними.
• Создать переменная для отслеживания текущего отсортированные элементы, изначально настроенные на array.length - 1, что угодно после сортировки.
• Итерация назад. Каждый раз, когда вы сталкиваетесь с 1:
  • поменять местами единицу и ее элемент перед ней с буквами U.
  • поменять местами U обратно на трекер отсортированных в данный момент элементов -1, обновить переменную
• Продолжить до начала массива.

Ну, первое, что приходит мне в голову, - это подход динамического программирования сверху вниз. Это довольно легко понять, но может съесть много памяти. Пока я пытаюсь применить восходящий подход, вы можете попробовать следующее:

Идея проста - кэшировать все результаты для поиска методом перебора. Это будет примерно так:

function findBestStep(currentArray, cache) {
    if (!cache.contains(currentArray)) {
        for (all possible moves) {
            find best move recursively
        }
        cache.set(currentArray, bestMove);
    } 

    return cache.get(currentArray);
}

Сложность этого метода будет ... O (2 ^ n), что жутко. Однако я не вижу логического способа, чтобы он мог быть меньше, поскольку разрешен любой ход.

Если найти способ применить восходящий алгоритм, он мог бы быть немного быстрее (ему не нужен кеш), но он все равно будет иметь сложность O (2 ^ n).

Добавлено: Хорошо, я реализовал это на Java. Код длинный, как всегда в Java, поэтому не пугайтесь его размера. Основной алгоритм довольно прост и находится внизу. Я не думаю, что может быть что-то быстрее, чем это (это скорее математический вопрос, если это может быть быстрее). Он потребляет тонны памяти, но все равно вычисляет все довольно быстро. Этот 0,1,0,1,0,1,0,1,0,1,0,1,0,1,2,2 вычисляет за 1 секунду, потребляя ~ 60 МБ памяти, что дает 7 пошаговая сортировка.

public class Main {

    public static final int UU_CODE = 2;

    public static void main(String[] args) {
        new Main();
    }

    private static class NumberSet {
        private final int uuPosition;
        private final int[] numberSet;
        private final NumberSet parent;

        public NumberSet(int[] numberSet) {
            this(numberSet, null, findUUPosition(numberSet));
        }

        public NumberSet(int[] numberSet, NumberSet parent, int uuPosition) {
            this.numberSet = numberSet;
            this.parent = parent;
            this.uuPosition = uuPosition;
        }

        public static int findUUPosition(int[] numberSet) {
            for (int i=0;i<numberSet.length;i++) {
                if (numberSet[i] == UU_CODE) {
                    return i;
                }
            }
            return -1;
        }

        protected NumberSet getNextNumberSet(int uuMovePos) {
            final int[] nextNumberSet = new int[numberSet.length];
            System.arraycopy(numberSet, 0, nextNumberSet, 0, numberSet.length);
            System.arraycopy(this.getNumberSet(), uuMovePos, nextNumberSet, uuPosition, 2);
            System.arraycopy(this.getNumberSet(), uuPosition, nextNumberSet, uuMovePos, 2);
            return new NumberSet(nextNumberSet, this, uuMovePos);
        }

        public Collection<NumberSet> getNextPositionalSteps() {
            final Collection<NumberSet> result = new LinkedList<NumberSet>();

            for (int i=0;i<=numberSet.length;i++) {
                final int[] nextNumberSet = new int[numberSet.length+2];
                System.arraycopy(numberSet, 0, nextNumberSet, 0, i);
                Arrays.fill(nextNumberSet, i, i+2, UU_CODE);
                System.arraycopy(numberSet, i, nextNumberSet, i+2, numberSet.length-i);
                result.add(new NumberSet(nextNumberSet, this, i));
            }
            return result;
        }

        public Collection<NumberSet> getNextSteps() {
            final Collection<NumberSet> result = new LinkedList<NumberSet>();

            for (int i=0;i<=uuPosition-2;i++) {
                result.add(getNextNumberSet(i));
            }

            for (int i=uuPosition+2;i<numberSet.length-1;i++) {
                result.add(getNextNumberSet(i));
            }

            return result;
        }

        public boolean isFinished() {
            boolean ones = false;
            for (int i=0;i<numberSet.length;i++) {
                if (numberSet[i] == 1)
                    ones = true;
                else if (numberSet[i] == 0 && ones)
                    return false;
            }
            return true;
        }

        @Override
        public boolean equals(Object obj) {
            if (obj == null) {
                return false;
            }
            if (getClass() != obj.getClass()) {
                return false;
            }
            final NumberSet other = (NumberSet) obj;
            if (!Arrays.equals(this.numberSet, other.numberSet)) {
                return false;
            }
            return true;
        }

        @Override
        public int hashCode() {
            int hash = 7;
            hash = 83 * hash + Arrays.hashCode(this.numberSet);
            return hash;
        }

        public int[] getNumberSet() {
            return this.numberSet;
        }

        public NumberSet getParent() {
            return parent;
        }

        public int getUUPosition() {
            return uuPosition;
        }
    }

    void precacheNumberMap(Map<NumberSet, NumberSet> setMap, int length, NumberSet endSet) {
        int[] startArray = new int[length*2];
        for (int i=0;i<length;i++) startArray[i]=0;
        for (int i=length;i<length*2;i++) startArray[i]=1;
        NumberSet currentSet = new NumberSet(startArray);

        Collection<NumberSet> nextSteps = currentSet.getNextPositionalSteps();
        List<NumberSet> nextNextSteps = new LinkedList<NumberSet>();
        int depth = 1;

        while (nextSteps.size() > 0) {
            for (NumberSet nextSet : nextSteps) {
                if (!setMap.containsKey(nextSet)) {
                    setMap.put(nextSet, nextSet);
                    nextNextSteps.addAll(nextSet.getNextSteps());
                    if (nextSet.equals(endSet)) {
                        return;
                    }
                }
            }
            nextSteps = nextNextSteps;
            nextNextSteps = new LinkedList<NumberSet>();
            depth++;
        }
    }

    public Main() {
        final Map<NumberSet, NumberSet> cache = new HashMap<NumberSet, NumberSet>();
        final NumberSet startSet = new NumberSet(new int[] {0,1,0,1,0,1,0,1,0,1,0,1,0,1,2,2});

        precacheNumberMap(cache, (startSet.getNumberSet().length-2)/2, startSet);

        if (cache.containsKey(startSet) == false) {
            System.out.println("No solutions");
        } else {
            NumberSet cachedSet = cache.get(startSet).getParent();
            while (cachedSet != null && cachedSet.parent != null) {
                System.out.println(cachedSet.getUUPosition());
                cachedSet = cachedSet.getParent();
            }
        }
    }
}

Вот попытка:

Start:
  let c1 = the total number of 1s
  let c0 = the total number of 0s
  if the UU is at the right end of the string, goto StartFromLeft
StartFromRight
  starting at the right end of the string, move left, counting 1s, 
  until you reach a 0 or the UU.  
  If you've reached the UU, goto StartFromLeft.
  If the count of 1s equals c1, you are done.  
  Else, swap UU with the 0 and its left neighbor if possible.  
  If not, goto StartFromLeft.
StartFromLeft
  starting at the left end of the string, move right, counting 0s,
  until you reach a 1 or the UU.
  If you've reached the UU, goto StartFromRight.
  If the count of 0s equals c0, you are done.
  Else, swap UU with the 1 and its right neighbor, if possible.  
  If not, goto StartFromRight
  Then goto StartFromRight.

Итак, для исходного 1100UU0011:

1100UU0011 - original
110000UU11 - start from right, swap UU with 00
UU00001111 - start from left, swap UU with 11

Для более сложного 0101UU01

0101UU01 - original
0UU11001 - start from right, can't swap UU with U0, so start from left and swap UU with 10
00011UU1 - start from right, swap UU with 00

Однако это не решит что-то вроде 01UU0 ... но это может быть исправлено флагом - если вы однажды прошли весь алгоритм, не сделали подкачки и он не решен ... сделайте что-нибудь.

Нас всего 2?

Почему бы просто не посчитать количество нулей и не сохранить положение нас:

numberOfZeros = 0
uPosition = []
for i, value in enumerate(sample):
    if value = 0:
        numberOfZeros += 1
    if value = U
       uPosition.append(i)

result = []
for i in range(len(sample)):
    if i = uPosition[0]
       result.append('U')
       uPosition.pop(0)
       continue
    if numberOfZeros > 0:
       result.append('0')
       numberOfZeros -= 1
       continue
    result.append('1')

Результатом будет время выполнения O (n)

Или даже лучше:

result = []
numberOfZeros = (len(sample)-2)/2
for i, value in enumerate(sample):
    if value = U
       result.append('U')
       continue
    if numberOfZeros > 0:
       result.append(0)
       numberOfZeros -= 1
       continue
    result.append(1)

Counting sort.

Если A - количество 0, A - количество 1, а U - количество Us:

for(int i=0; i<A; i++)
   data[i] = '0';
for(int i=0; i<A; i++)
   data[A+i] = '1';
for(int i=0; i<U; i++)
   data[A+A+i] = 'U';

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

Задача размера n - это задача, имеющая ровно n нулей, n единиц и два Us, следовательно, она состоит из 2n+2 символов.

Существуют

(2n)!
-----
(n!)²

различные последовательности, состоящие ровно из n нулей и nединиц. Тогда существует 2n+1 возможных позиций для вставки двух Us, следовательно, существует

(2n)!         (2n+1)!
-----(2n+1) = -------
(n!)²          (n!)²

проблемных экземпляров размером n.

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

Экземпляры размера один либо уже отсортированы

--01   0--1   01--

(я думаю, что буду использовать дефисы вместо Us, потому что их легче распознать), либо не могут быть отсортированы.

--10  ==only valid move==>  10--
-10-  no valid move
10--  ==only valid move==>  --10

Вследствие этого я буду считать, что n >= 2.

Я думаю об обратной задаче - какие неупорядоченные последовательности можно получить, начиная с упорядоченной последовательности. Упорядоченные последовательности определены вплоть до расположения обоих дефисов - поэтому следующий вопрос заключается в том, можно ли достичь любой упорядоченной последовательности из любой другой упорядоченной последовательности. Поскольку последовательность ходов может быть выполнена вперед и назад, достаточно показать, что одна конкретная упорядоченная последовательность достижима из всех остальных. Я выбираю (0|n)(1|n)--. ((0|x) представляет собой ровно x нулей. Если x не имеет формы n-m, то предполагается нуль или больше. Могут существовать дополнительные ограничения типа a+b+2=n, не указанные в явном виде. ^^ указывает на позицию подкачки. Граница 0/1, очевидно, находится между последним нулем и первой единицей.)

// n >= 2, at least two zeros between -- and the 0/1 border
(0|a)--(0|b)00(1|n) => (0|n)--(1|n-2)11 => (0|n)(1|n)--
            ^^                       ^^
// n >= 3, one zero between -- and 0/1 boarder
(0|n-1)--01(1|n-1) => (0|n)1--(1|n-3)11 => (0|n)(1|n)--
         ^^                          ^^
// n >= 2, -- after last zero but at least two ones after --          
(0|n)(1|a)--(1|b)11 => (0|n)(1|n)--
                 ^^
// n >= 3, exactly one one after --
(0|n)(1|n-3)11--1 => (0|n)(1|n-3)--111 => (0|n)(1|n)--
            ^^                      ^^
// n >= 0, nothing to move
(0|n)(1|n)--

Для оставшихся двух задач размера два - 0--011 и 001--1 - кажется, невозможно достичь 0011--. Таким образом, для n >= 3 можно получить любую упорядоченную последовательность из любой другой упорядоченной последовательности максимум за четыре хода (Возможно, меньше во всех случаях, потому что я думаю, что было бы лучше выбрать (0|n)--(1|n), но я оставляю это на завтра). Предварительная цель - выяснить, с какой скоростью и при каких условиях можно создать (и, следовательно, удалить) 010 и 101, потому что они кажутся трудными случаями, как уже упоминалось другими.