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

Ответ 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"

Ответ 2

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

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

Ответ 3

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

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

Есть

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

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

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

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

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

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

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

Ответ 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();
            }
        }
    }
}

Ответ 5

Вот пример:

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

Ответ 6

О вопросе... Он никогда не просил оптимального решения, и эти типы вопросов этого не хотят. Вам нужно написать алгоритм общего назначения для решения этой проблемы, и поиск грубой силы для поиска наилучшего решения невозможен для строк, длина которых может быть мегабайт. Также я заметил поздно, что гарантировано будет такое же количество 0 и 1, но я думаю, что более интересно работать с общим случаем, где могут быть разные числа 0 и 1. На самом деле не гарантируется решение в каждом случае, если длина входной строки меньше 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. Это переместит все 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.

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

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

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

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

Вызов:

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

Ответ 7

Сортировка сортировки.

Если A - число 0s, A также является числом 1s, а 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';

Ответ 8

Есть только 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)