Interesante problema de clasificación

Question

Hay unos, ceros y 'U's en un orden particular. (Por ejemplo, "1001UU0011") El número de ceros y ceros es el mismo, y siempre hay dos 'U' uno al lado del otro. Puedes intercambiar el par de 'U's con cualquier par de dígitos adyacentes. Aquí hay un movimiento de muestra:

 __ 
    /\ 
1100UU0011 --> 11001100UU 

La tarea es poner todos los ceros antes de los.

Aquí es una solución de muestra:

First step: 
    __ 
/\ 
1100UU0011 

Second step: 
    ____ 
/ \ 
UU00110011 

000011UU11 --> DONE 

Es bastante fácil crear un algoritmo de fuerza bruta. Pero con eso se necesitan cientos o incluso miles de movimientos para resolver uno simple como mi ejemplo. Así que estoy buscando algo más algoritmo "inteligente".

---

No es tarea; era una tarea en una competencia. El concurso ha terminado pero no puedo encontrar la solución para esto.

Editar: La tarea aquí es crear un algoritmo que pueda ordenar esos 0 y 1, no solo los resultados N 0 y N 1 y 2 Us. Tienes que mostrar los pasos de alguna manera, como en mi ejemplo.

Editar 2: La tarea no solicitó el resultado con la menor cantidad de movimientos ni nada de eso. Pero personalmente me encantaría ver un algoritmo que proporciona :)

Answer 1

Si usa una fuerza bruta ANCHA-primero, sigue siendo fuerza bruta, pero al menos se garantiza que obtendrá la secuencia más corta de movimientos, si hay alguna respuesta. Aquí hay una solución rápida de Python que utiliza una búsqueda de ancho primero.

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.

Si A es el número de 0s, A es también el número de 1s, y T es el número de nosotros:

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

Hay solamente 2?

Por qué no simplemente contar el número de 0s y almacenar la posición de los EE.UU.:

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

daría lugar a un tiempo de ejecución de O (n)

O aún mejor:

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

Bueno, lo primero que se me ocurre es un enfoque de programación dinámica de arriba hacia abajo. Es algo fácil de entender pero podría comer mucha memoria. Mientras intento aplicar un enfoque ascendente, puede probar este:

La idea es simple: guarde en caché todos los resultados para la búsqueda de fuerza bruta. Se convertirá en algo como esto:

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

    return cache.get(currentArray); 
} 

La complejidad de este método sería ... O (2^n) que es espeluznante. Sin embargo, no veo una forma lógica de que pueda ser más pequeño ya que se permite cualquier movimiento.

Si encuentra una manera de aplicar el algoritmo ascendente, podría ser un poco más rápido (no necesita un caché) pero aún tendrá complejidad O (2^n).

Agregado: Bien, lo he implementado en Java. El código es largo, como siempre lo está en Java, así que no te asustes de su tamaño.El algoritmo principal es bastante simple y se puede encontrar en la parte inferior. No creo que haya manera más rápida que esto (esta es más una pregunta matemática si puede ser más rápido). Come toneladas de memoria pero todavía lo calcula bastante rápido. Este 0,1,0,1,0,1,0,1,0,1,0,1,0,1,2,2 computa en 1 segundo, consume ~ 60mb de memoria, lo que resulta en una clasificación de 7 pasos.

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

creo que esto debería funcionar:

• Iterar vez para encontrar la posición de la U de. Si no ocupan los últimos dos puntos , muévalos allí por intercambiando con los dos últimos.
• crear una variable para rastrear los elementos actualmente ordenados, establecido inicialmente en Array.length - 1, lo que significa nada después de que se ordena.
• Iterar hacia atrás. Cada vez que encuentre un 1:
  • intercambie el uno y su elemento antes con las U.
  • de intercambio posterior de la U a la los elementos actualmente ordenados rastreador -1, actualizar la variable
• continuará hasta que el comienzo de la matriz.

Answer 6

Aquí hay una oportunidad:

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. 

Por lo tanto, para el original 1100UU0011:

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

Para el complicado 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 

Sin embargo, esto no va a resolver algo así como 01UU0 ... pero eso podría ser fijado por una bandera: si ha pasado por el algoritmo completo una vez, no ha realizado ningún intercambio y no está resuelto ... haga algo.

Answer 7

Esto es un problema bastante interesante, así que vamos a tratar de resolverlo. Comenzaré con un análisis preciso del problema y veré lo que uno puede descubrir. Añadiré pieza por pieza a esta respuesta en los próximos días. Cualquier ayuda es bienvenida.

un problema de tamaño n es un problema con exactamente exactamente n ceros, n queridos, y dos U s, por lo tanto, consiste en 2n+2 símbolos.

Hay

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

secuencias diferentes de exactamente n ceros y n queridos.Luego están 2n+1 posiciones es posible insertar las dos U s, por lo tanto, hay

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

casos problema del tamaño n.

Siguiente Estoy buscando una forma de asignar una puntuación a cada instancia de problema y cómo esta puntuación cambia bajo todas las movidas posibles con la esperanza de averiguar cuál es el número mínimo de movimientos requeridos.

Instancia de tamaño de uno están ya ordenadas

--01 0--1 01-- 

(creo que voy a utilizar guiones en lugar de U s porque son más fáciles de reconocer) o no se pueden ordenar.

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

En consecuencia asumiré n >= 2.

Estoy pensando en el problema inverso: qué secuencias desordenadas se pueden alcanzar a partir de una secuencia ordenada. Las secuencias ordenadas se determinan hasta la ubicación de ambos guiones, por lo que la siguiente pregunta es si es posible llegar a cada secuencia ordenada de cada secuencia de orden. Debido a que una secuencia de movimientos se puede realizar hacia adelante y hacia atrás, es suficiente para mostrar que una secuencia ordenada específica es accesible desde cualquier otra. Elijo (0|n)(1|n)--. ((0|x) representa exactamente x ceros. Si x no es de la forma n-m se asume cero o más. Puede haber restricciones adicionales como a+b+2=n no indicadas explícitamente ^^ indica la posición de intercambio. El borde 0/1 está obviamente entre el último cero y primero)

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

para los dos problemas restantes del tamaño de dos -. 0--011 y 001--1 - no parece ser posible llegar a 0011--. Entonces, para n >= 3 es posible llegar a cada secuencia ordenada de cualquier otra secuencia ordenada en un máximo de cuatro movimientos (Probablemente menos en todos los casos porque creo que hubiera sido mejor elegir (0|n)--(1|n) pero lo dejo para mañana). El objetivo preliminar es averiguar a qué velocidad y bajo qué condiciones se puede crear (y en consecuencia eliminar) 010 y 101 porque parecen ser los casos difíciles ya mencionados por otros.

Answer 8

Acerca de la pregunta ... Nunca pidió la solución óptima y este tipo de preguntas no quiere eso. Necesita escribir un algoritmo de propósito general para manejar este problema y una búsqueda de fuerza bruta para encontrar la mejor solución no es factible para las cadenas que pueden tener megabytes de longitud. También noté tarde que se garantiza que habrá el mismo número de 0 y 1, pero creo que es más interesante trabajar con el caso general en el que puede haber diferentes números de 0 y 1. En realidad, no se garantiza que sea una solución en todos los casos si la longitud de la cadena de entrada es menor que 7, incluso en el caso en que tenga 2 0s y 2 1s.

Tamaño 3: Sólo un dígito por lo que está ordenada por definición (UU0 UU1 0UU 1UU)

Tamaño 4: No hay manera de alterar el orden. No hay movimientos si UU está en el medio, y solo se intercambia con ambos dígitos si está al final (1UU0 sin movimientos, UU10-> 10UU-> UU10, etc.)

Tamaño 5: UU en el centro puede solo mueva al extremo y no cambie el orden de los 0s y 1s (1UU10-> 110UU).UU en un extremo puede moverse a la mitad y no cambiar el orden, pero solo volver al mismo extremo para que no le sirva (UU110-> 11UU0-> UU110). La única forma de cambiar los dígitos es si el UU está en un extremo y se intercambia con el extremo opuesto. (UUABC-> BCAUU o ABCUU-> UUCAB). Esto significa que si UU está en las posiciones 0 o 2 puede resolver si 0 está en el medio (UU101-> 011UU o UU100-> 001UU) y si UU está en las posiciones 1 o 3 puede resolver si 1 está en el medio (010UU-> UU001 o 110UU-> UU011). Cualquier otra cosa ya está resuelta o no puede resolverse. Si necesitamos manejar este caso, diría que es un código duro. Si está ordenado, devuelve el resultado (sin movimientos). Si UU está en el medio en alguna parte, muévelo hasta el final. Cambie desde el final al otro extremo y ese es el único intercambio posible, ya sea que esté ordenado o no.

Tamaño 6: Ahora tenemos una posición en la que podemos tener una cadena especificada de acuerdo con las reglas donde podemos realizar movimientos pero donde no puede haber solución. Este es el punto problemático con cualquier algoritmo, porque creo que una condición de cualquier solución debería ser que te avisará si no se puede resolver. Por ejemplo, 0010, 0100, 1000, 1011, 1100, 1101 y 1110 se pueden resolver sin importar dónde se ubique el UU y los peores casos tardan 4 movimientos en resolverse. 0101 y 1010 solo pueden resolverse si UU está en una posición impar. 0110 y 1001 solo pueden resolverse si UU se encuentra en una posición pareja (final o central).

Creo que la mejor manera será algo como lo siguiente, pero aún no lo he escrito. Primero, asegúrese de colocar un '1' al final de la lista. Si el final es actualmente 0, mueva UU hasta el final y luego muévala a la última posición '1': 1. Después de eso, mueva continuamente UU al primer '1', luego al primer '0' después de la nueva UU. Esto moverá todos los 0 al comienzo de la lista. He visto una respuesta similar en el otro sentido, pero no tuvo en cuenta el personaje final en ninguno de los extremos. Esto puede dar lugar a problemas con valores pequeños aún (es decir, 001UU01, no se puede mover al primer 1, mover al final 00101UU nos permite movernos al inicio pero deja 0 al final 00UU110).

Supongo que se pueden codificar casos especiales como ese. Sin embargo, creo que puede haber un algoritmo mejor. Por ejemplo, podría usar los dos primeros caracteres como una 'variable de intercambio temporal. Pondría UU allí y luego haría combinaciones de operaciones en otros para dejar atrás a UY al comienzo. Por ejemplo, UUABCDE puede intercambiar AB con CD o DE o BC CON DE (BCAUUDE-> BCADEUU-> UUADEBC).

Otra cosa posible sería tratar los caracteres como dos bloques de dos bits base-3 0101UU0101 se mostrará como 11C11 o 3593. Tal vez también algo así como una combinación de intercambios codificados. Por ejemplo, si alguna vez ves 11UU, mueve UU a la izquierda 2. Si alguna vez ves UU00, mueve UU a la derecha dos. Si ve UU100, o UU101, mueva UU a la derecha 2 para obtener 001UU o 011UU.

Tal vez otra posibilidad sería algún algoritmo para mover 0s izquierda del centro y derecha 1s del centro (si se da que hay el mismo número de 0s y 1s.

Tal vez sería mejor trabajar en una estructura que solo contenía 0 y 1 con una posición para UU.

Quizás observe mejor la condición resultante, permitiendo que UU esté en cualquier lugar de la cadena, estas condiciones DEBEN cumplirse: No hay 0 después de Length/2 No 1s antes (Longitud/2-1)

Quizás th Hay reglas más generales, como que es realmente bueno intercambiar UU con 10 en este caso '10111UU0' porque un '0' está después de UU ahora y eso le permitiría mover el nuevo 00 al lugar donde estaba el 10 (10111UU0-> UU111100 -> 001111UU).

De todos modos, aquí está el código de fuerza bruta en C#. La entrada es una cadena y un diccionario vacío.Se llena el diccionario con todas las posibles cadena resultante como las claves y la lista de pasos más cortos para llegar allí como el valor:

Llamar:

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

Incluye DoTests() que llama DoSort para cada cadena sea posible con la cantidad dada de dígitos (sin incluir 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(); 
    } 
    } 
} 
}