Espaciado de elementos en una matriz circular

Question

Este es un problema interesante que he encontrado que creo que debería tener una solución elegante y comprobable, pero no he podido obtenerlo del todo. He definido como:

definir una función que toma como entrada un conjunto de N elementos y un número entero R positiva, y devuelve una matriz circular (o una matriz que trata como circular) cuando no dos elementos idénticos son menos que R aparte, o un nulo si tal ordenamiento no es posible.

Así f([a,b,d,c,a,d,k,a,d], 3) podría volver [a,b,d,a,k,d,a,c,d], pero f([a,b,d,c,a,d,k,a,d,a,a], 3) volvería null. Defino dos elementos como R apart si tienen elementos R-1 entre ellos, por lo que en el conjunto [x,a,b,y], x y y están 3 separados por un lado y 0 separados por el otro.

Siento que esta sería una gran pregunta para la entrevista también.

Answer 1

1. Divida la matriz en grupos de elementos idénticos (con clasificación o usando una tabla hash).
2. Encuentra el grupo más grande. Si su tamaño es mayor que floor(N/R), devuelva nulo.
3. Si el tamaño del grupo más grande es igual a exactamente N/R, particione (clasifique parcialmente) la lista de grupos, de modo que todos los grupos de tamaño N/R sean los primeros en el siguiente paso.
4. Para cada grupo, coloque sus elementos en la matriz de resultados (memoria intermedia circular), incrementando el índice en R, mientras sea posible. Si R y N no son coprima, a veces, después de N/GCD(N,R) incrementos, el índice apuntará al elemento ya utilizado. En tales casos, incremente el índice por R+1 en lugar de R y continúe.

Answer 2

Siento un poco de mal humor allí. No hago esto por puntos. Lo hago porque lo disfruto. Te di mucho y pensé que podrías llevarlo por tu cuenta. De todos modos, este es un lugar donde completos extraños ayudan a completar extraños.

Aquí es un código, con los resultados de las pruebas siguientes:

import java.util.ArrayList; 
import java.util.Arrays; 
import java.util.HashMap; 
import java.util.List; 
import java.util.Map; 

public class ResolvingAlgo { 

public static Character[] resolver(Character[] objects, int R) { 
    //calculate frequency of each element 
    Map<Character, Integer> map = new HashMap<Character, Integer>(); 
    for (Character c : objects) { 
     Integer freq = map.get(c); 
     map.put(c, (freq == null) ? 1 : freq + 1); 
    } 
    //count elements with frequency R 
    List<Character> pillars = new ArrayList<Character>(); 
    for (Character c : map.keySet()) { 
     int freq = map.get(c); 
     if (R == freq) { 
      pillars.add(c); 
     } else if (objects.length/R < freq) { 
      return null; 
     } 
    } 
    //output array 
    Character output[] = new Character[objects.length]; 
    //load the pillars R+1 apart 
    int skip = (pillars.size()<R)?R:R+1; 
    for (Character c : pillars) { 
     int index = 0; 
     for (int out=index; out<output.length; out++) { 
      if (output[out] == null) { 
       break; 
      } 
      index++; 
     } 
     for (int i = R; i > 0; i--) { 
      output[index] = c; 
      index += skip; 
     } 
     map.remove(c); 
    }//pillars 
    //add remainders 
    while (!map.isEmpty()) { 
     int index = 0; 
     Character keyset[] = Arrays.copyOf(map.keySet().toArray(new Character[0]), map.size()); 
     for (Character c : keyset) { 
      for (int out = index; out < output.length; out++) { 
       if (null == output[out]) { 
        break; 
       } 
       index++; 
      } 
      output[index] = c; 
      int freq = map.get(c); 
      if (freq <= 1) { 
       map.remove(c); 
      } else { 
       map.put(c, freq - 1); 
      } 
     }//for keyset 
    }//while 
    return output; 
}//resolver 

public static void main(String... args) { 
    Character[][] input = { 
     {'a', 'a', 'a', 'b', 'b', 'b', 'c', 'c', 'c', 'd', 'd', 'd'}, 
     {'a', 'a', 'a', 'b', 'b', 'b', 'c', 'c', 'c', 'd', 'd', 'k'}, 
     {'a', 'a', 'a', 'b', 'c', 'd', 'd', 'd', 'k'}, 
     {'a', 'b', 'd', 'c', 'a', 'd', 'k', 'a', 'd', 'a', 'a'}, 
     {'a', 'a', 'a', 'a', 'b', 'b', 'b', 'c', 'c', 'c', 'd', 'd'}, 
     {'a', 'b', 'c', 'd', 'e', 'f', 'a', 'b', 'c', 'd', 'e', 'f'}, 
     {'a','b','c','d','a','b','c','d'} 
    }; 
    for(Character in[]: input) 
     System.out.println(Arrays.toString(resolver(in, 3))); 
} 
} 

Resultado de la prueba:

[d, b, c, a, d, b, c, a, d, b, c, a] 
[b, c, a, d, b, c, a, k, b, c, a, d] 
[d, a, b, d, a, c, d, a, k] 
null 
[b, c, d, b, c, a, b, c, d, a, a, a] 
[f, d, e, b, c, a, f, d, e, b, c, a] 
[d, b, c, a, d, b, c, a] 

Answer 3

Advertencia: Esta no es una solución. Es solo una reformulación.

Para el montaje de la notación, dicen que hay m diferentes tipos de elementos (como se puede llamar al entonces 1,2,...,m) y hay a_i elementos de tipo i. Entonces tenemos a_1 + ... + a_m = N.

Sea G(N,R) el gráfico con los vértices v1, v2, ..., vN donde hay un borde vi <--> vj cuando |i-j| mod N < R. Por ejemplo, G(N,2) es N -cycle. La pregunta pide un proper coloring del N -cycle con a_i vértices de color i.

En este contexto, la pregunta es equivalente a calcular los coeficientes distintos de cero de Stanley's chromatic symmetric function. Esto puede no facilitar el problema, pero ciertamente lo hace más interesante en mi mente. Por ejemplo, creo que la respuesta es conocida por G(N,2), algo así como iff max(a_i) <= N/2 (ciertamente no existe una solución si alguna a_i > N/R). Voy a actualizar esta no respuesta después de un poco más de investigación.

Answer 4

lo siento, me siento tonto aquí, pero no entiendo las objeciones a la solución de Evgeny. Creo que el siguiente código implementa lo que sugieren (excepto que arrojo un error en lugar de devolver nulo) y funciona bien con la secuencia que se supone que es problemática.

estoy publicando esto como una respuesta en gran parte porque quiero publicar el código para su corrección. presumiblemente tiene el mismo problema que la respuesta anterior, ¿por qué alguien puede explicar cuál es el problema?

(ps en mi caso, los grupos también están ordenados por longitud, lo que no se da explícitamente antes).

from collections import Counter, defaultdict 

def ring(n, text): 
    result = [None for t in text] 
    index = 0 
    for c in Counter(text).elements(): 
     while result[index] is not None: 
      index = (index + 1) % len(result) 
     result[index] = c 
     index = (index + n) % len(result) 
    loop = ''.join(result) 
    print(text, ' -> ', loop) 
    check(n, loop) 

def check(n, text): 
    loop = text + text 
    last = defaultdict(lambda: -n) 
    for (i,c) in enumerate(loop): 
     assert i - last[c] >= n, (c, i - last[c]) 
     last[c] = i 

ring(3, 'aaaabbbcccdd') # problematic according to B_? 
ring(3, 'abdcadkad') # given in question 
ring(3, 'abdcadkadaa') # given in question, expected to fail 

y en ejecución:

> python3.2 ring.py 
aaaabbbcccdd -> acbacbacdabd 
abdcadkad -> akdacdabd 
abdcadkadaa -> aadakdacdab 
Traceback (most recent call last): 
    File "ring.py", line 25, in <module> 
    ring(3, 'abdcadkadaa') 
    File "ring.py", line 14, in ring 
    check(n, loop) 
    File "ring.py", line 20, in check 
    assert i - last[c] >= n, (c, i - last[c]) 
AssertionError: ('a', 1)