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

Question

Есть единицы, нули и 'U' в определенном порядке.(Например, «1001UU0011») Число единиц и нулей одинаково, и всегда есть два U рядом друг с другом.Вы можете поменять пару U на любую пару соседних цифр.Вот пример хода:

      __
     /  \
1100UU0011 --> 11001100UU

Задача состоит в том, чтобы поставить все нули перед единицами.

Вот пример решения:

First step:
  __
 /  \
1100UU0011

Second step:
  ____
 /    \
UU00110011

000011UU11  --> DONE

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

---

Это не домашняя работа;это было задание в соревновании.Конкурс окончен, но я не могу найти решение для этого.

Редактировать : Задача здесь состоит в том, чтобы создать алгоритм, который может сортировать эти 0 и 1, а не просто выводить N 0sи N 1s и 2 Us.Вы должны как-то показать шаги, как в моем примере.

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

Answer 1

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

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

Answer 2

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

Проблема размера n - это проблема с точно точно n нулями, n единицами и двумя U с, следовательно, она состоит из 2n+2 символов.

Есть

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

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

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

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

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

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

--01   0--1   01--

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

--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, поскольку они кажутся трудными случаями, как уже упоминалось другими.

Answer 3

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

from time import time

def generate(c):
    sep = "UU"
    c1, c2 = c.split(sep)
    for a in range(len(c1)-1):
        yield c1[0:a]+sep+c1[(a+2):]+c1[a:(a+2)]+c2
    for a in range(len(c2)-1):
        yield c1+c2[a:(a+2)]+c2[0:a]+sep+c2[(a+2):]

def solve(moves,used):
    solved = [cl for cl in moves if cl[-1].rindex('0') < cl[-1].index('1')]
    if len(solved) > 0: return solved[0]
    return solve([cl+[d] for cl in moves for d in generate(cl[-1]) if d not in used and not used.add(d)],used)

code = raw_input('enter the code:')

a = time()
print solve([[code]],set())
print "elapsed time:",(time()-a),"seconds"

Answer 4

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

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

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

Answer 5

О вопросе ... Он никогда не просил оптимального решения, и эти типы вопросов не хотят этого. Вам нужно написать алгоритм общего назначения для решения этой проблемы, и поиск методом «грубой силы», чтобы найти лучшее решение, невозможен для строк, длина которых может быть мегабайтом. Также я поздно заметил, что гарантированно будет одинаковое количество нулей и единиц, но я думаю, что более интересно работать с общим случаем, когда могут быть разные числа нулей и единиц. На самом деле не гарантируется, что будет решение в каждом случае, если длина входной строки меньше 7, даже в том случае, если у вас 2 0 и 2 1.

Размер 3: только одна цифра, поэтому она сортируется по определению (UU0 UU1 0UU 1UU)

Размер 4: Нет способа изменить порядок. Ходов нет, если UU находится посередине, и только замена обеих цифр, если они заканчиваются (1UU0 без ходов, UU10-> 10UU-> UU10 и т. Д.)

Размер 5: UU в середине может перемещаться только на дальний конец и не изменять порядок 0 и 1 (1UU10-> 110UU). UU на конце может перемещаться в середину и не изменять порядок, а только возвращаться к тому же концу, поэтому его бесполезно (UU110-> 11UU0-> UU110). Единственный способ изменить цифры - это если UU находится в конце и поменяться с противоположным концом. (UUABC-> BCAUU или ABCUU-> UUCAB). Это означает, что если UU находится в позициях 0 или 2, он может решить, находится ли 0 в середине (UU101-> 011UU или UU100-> 001UU), и если UU находится в позициях 1 или 3, он может решить, находится ли 1 в середине ( 010UU-> UU001 или 110UU-> UU011). Все остальное уже решено или неразрешимо. Если нам нужно разобраться с этим делом, я бы сказал, жестко закодировать его. Если отсортировано, вернуть результат (без ходов). Если UU где-то посередине, переместите его до конца. Поменяйте местами с конца на другой конец, и это единственно возможный обмен, независимо от того, отсортирован он сейчас или нет.

Размер 6: Теперь мы получаем позицию, в которой мы можем указать строку в соответствии с правилами, где мы можем делать ходы, но где не может быть решения. В этом и заключается проблема любого алгоритма, потому что я думаю, что условием любого решения должно быть то, что оно сообщит вам, если оно не может быть решено. Например, 0010, 0100, 1000, 1011, 1100, 1101 и 1110 могут быть решены независимо от того, где находится UU, а наихудшие случаи требуют 4 хода для решения. 0101 и 1010 могут быть решены, только если UU находится в нечетном положении. 0110 и 1001 могут быть решены, только если UU находится в четном положении (либо в конце, либо в середине).

Я думаю, что лучшим способом будет что-то вроде следующего, но я еще не написал это. Во-первых, убедитесь, что вы ставите «1» в конце списка. Если конец в настоящий момент равен 0, переместите UU в конец, затем переместите его в последнюю позицию «1» - 1. После этого вы постоянно перемещаете UU к первому «1», а затем к первому «0» после нового UU. Это переместит все 0 в начало списка. Я видел аналогичный ответ с другой стороны, но он не учитывал окончательный характер с обеих сторон. Это может привести к проблемам с небольшими значениями (например, 001UU01, невозможно перейти к первому 1, перейти к концу, 00101UU позволяет нам перейти к началу, но оставляет 0 в конце 00UU110).

Я предполагаю, что вы можете жестко запрограммировать такие особые случаи. Я думаю, что может быть лучший алгоритм, хотя. Например, вы можете использовать первые два символа как временную переменную подкачки. Вы бы поместили UU тут же, а затем выполняли комбинации операций над другими, чтобы оставить UY в начале. Например, UUABCDE может поменять AB с CD или DE или BC с DE (BCAUUDE-> BCADEUU-> UUADEBC).

Другой возможной вещью было бы рассматривать символы как два блока из двух битов base-3 0101UU0101 будет отображаться как 11C11 или 3593. Может также быть что-то вроде комбинации жестко закодированных свопов. Например, если вы когда-либо видите 11UU, переместите UU влево 2. Если вы когда-либо увидите UU00, переместите UU вправо на два. Если вы видите UU100 или UU101, переместите UU вправо 2, чтобы получить 001UU или 011UU.

Может быть, другой возможностью был бы некоторый алгоритм для перемещения нулей влево от центра и 1 секунд вправо от центра (если дано, что есть одинаковое количество нулей и 1сек.

Может быть, было бы лучше поработатьдля структуры, которая содержит только 0 и 1 с позицией для UU.

Может быть, лучше посмотреть на результирующее условие, позволяя UU находиться где-нибудь в строке, эти условия ДОЛЖНЫ быть выполнены: нет 0 с после длины/ 2 No 1s before (Длина / 2-1)

Возможно, есть более общие правила, например, действительно полезно поменять UU на 10 в этом случае на 10111UU0, потому что теперь 0 стоит после UU иэто позволит вам переместить новый 00 обратно туда, где было 10 (10111UU0-> UU111100-> 001111UU).

В любом случае, вот код грубой силы в C #. Входные данные представляют собой строку и пустой словарь.Он заполняет словарь каждой возможной результирующей строкой в ​​качестве ключей и списком кратчайших шагов, чтобы получить его в качестве значения:

Вызов:

m_Steps = new Dictionary<string, List<string>>();
DoSort("UU1010011101", new List<string>);

Включает DoTests ()который вызывает DoSort для каждой возможной строки с заданным количеством цифр (не включая UU):

Dictionary<string, List<string>> m_Steps = new Dictionary<string, List<string>>();

public void DoStep(string state, List<string> moves) {
 if (m_Steps.ContainsKey(state) && m_Steps[state].Count <= moves.Count + 1) // have better already
  return;

 // we have a better (or new) solution to get to this state, so set it to the moves we used to get here
 List<string> newMoves = new List<string>(moves);
 newMoves.Add(state);
 m_Steps[state] = newMoves;

 // if the state is a valid solution, stop here
 if (state.IndexOf('1') > state.LastIndexOf('0'))
  return;

 // try all moves
 int upos = state.IndexOf('U');
 for (int i = 0; i < state.Length - 1; i++) {
  // need to be at least 2 before or 2 after the UU position (00UU11 upos is 2, so can only move to 0 or 4)
  if (i > upos - 2 && i < upos + 2)
   continue;

  char[] chars = state.ToCharArray();
  chars[upos] = chars[i];
  chars[upos + 1] = chars[i + 1];
  chars[i] = chars[i + 1] = 'U';
  DoStep(new String(chars), newMoves);
 }
}

public void DoTests(int digits) { // try all combinations
 char[] chars = new char[digits + 2];
 for (int value = 0; value < (2 << digits); value++) {
  for (int uupos = 0; uupos < chars.Length - 1; uupos++) {
   for (int i = 0; i < chars.Length; i++) {
    if (i < uupos)
     chars[i] = ((value >> i) & 0x01) > 0 ? '1' : '0';
    else if (i > uupos + 1)
     chars[i] = ((value >> (i - 2)) & 0x01) > 0 ? '1' : '0';
    else
     chars[i] = 'U';
   }
   m_Steps = new Dictionary<string, List<string>>();
   DoSort(new string(chars), new List<string>);
   foreach (string key in m_Steps.AllKeys))
    if (key.IndexOf('1') > key.LastIndexOf('0')) { // winner
     foreach (string step in m_Steps[key])
      Console.Write("{0}\t", step);
     Console.WriteLine();
    }
  }
 }
}

Answer 6

Вот попытка:

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 ... но это можно исправить с помощью флага - если вы один раз прошли весь алгоритм, не сделали перестановок и он не был решен ... сделайте что-нибудь.

Answer 7

Есть только 2 Us?

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

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)

Answer 8

Подсчет сортировки .

Если 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';