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

Question

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

 __ 
    /\ 
1100UU0011 --> 11001100UU 

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

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

First step: 
    __ 
/\ 
1100UU0011 

Second step: 
    ____ 
/ \ 
UU00110011 

000011UU11 --> DONE 

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

---

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

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

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

Answer 1

Если вы используете первую грубую силу 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 2

Counting sort.

Если А число 0s, А также количество 1s, и U является число нас:

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'; 

Answer 3

Есть только 2 нас?

Почему не просто посчитать количество 0s и сохранить позицию компании:

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') 

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

Или еще лучше:

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 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

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

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

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

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

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

Есть

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

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

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

проблемные случаи размера n.

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

Instance размера одного либо уже отсортирован

--01 0--1 01-- 

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

--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 8

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

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

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

Размер 5: UU в середине может только перемещайтесь в дальний конец и не меняйте порядок 0s и 1s (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. Это переместит все 0s в начало списка. Я видел подобный ответ в обратном порядке, но он не принимал во внимание конечного персонажа с обоих концов. Это может привести к проблемам с небольшими значениями (т. Е. 001UU01, не может перейти к первому 1, перейти к концу 00101UU позволяет нам двигаться, чтобы начать, но оставляет 0 в конце 00UU110).

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

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

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

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

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

Возможно, ere являются более общими правилами, так как это действительно хорошо, чтобы поменять 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):