12

Estamos poniendo las bolas en un número fijo unos contenedores. Estos contenedores comienzan vacíos.

Empty bin (a=4): 0 0 0 0

Y uno por uno agregamos bolas a los contenedores.

0 0 0 1  or
0 0 1 0  or
0 1 0 0  or
1 0 0 0

Necesitamos una forma rápida de recorrer todos los estados posibles que toman los contenedores, sin duplicados y sin perder ninguno, y no queremos enumerar todos los contenedores posibles. Entonces, en cambio, asignamos a cada configuración bin un índice.

Asignamos el índice ordenando las configuraciones posibles de una manera específica:

Ordenar ascendente por suma: primero 0 0 0 0, luego las configuraciones posibles con 1 bola agregada, luego 2, etc.
Luego ordene dentro de cada suma en orden ascendente, desde el primer contenedor hasta el último:
```
0 0 0 2
0 0 1 1
0 0 2 0 
0 1 0 1
0 1 1 0 
0 2 0 0 
etc
```

Luego se asigna el índice ascendente a través de esta lista:

0 0 0 0  -> 1
0 0 0 1  -> 2
0 0 1 0  -> 3
0 1 0 0  -> 4
1 0 0 0  -> 5
0 0 0 2  -> 6
0 0 1 1  -> 7
0 0 2 0  -> 8
0 1 0 1  -> 9
0 1 1 0  -> 10
0 2 0 0  -> 11

Reglas

Cree una función o programa que tome una lista de cualquier tamaño con enteros no negativos e imprima o muestre su índice. Se puede suponer un ser de al menos 2. cortos victorias de código. Puede usar salida indexada 0 o indexada 1, pero especifique cuál usa. NB: todos los ejemplos aquí están indexados en 1.

Código de ejemplo

No golf, en R:

nodetoindex <- function(node){
  a <- length(node)
  t <- sum(node)
  if(t == 0) return(1)

  index <- choose(t-1 + a, a)

  while(sum(node) != 0){
    x <- node[1]
    sumrest <- sum(node)
    if(x == 0){
      node <- node[-1]
      next
    }
    a <- length(node[-1])
    index <- index + choose(sumrest + a, a) - choose(sumrest - x + a, a)
    node <- node[-1]
  }
  return(index + 1)
}

Casos de prueba

10 10 10 10 -> 130571
3 1 4 1 5 9 -> 424407
2 9 -> 69
0 0 0 -> 1
0 0 1 -> 2
0 0 0 0 0 0 -> 1
1 0 0 0 0 1 -> 23

code-golf number combinatorics JAD
fuente

¿Cómo funciona la clasificación a través del valor numérico de la concatenación cuando los recuentos tienen diferentes números de dígitos?

TheBikingViking

@TheBikingViking hmm, no había pensado en eso, cambié la redacción para reflejar el código de ejemplo y los casos de prueba. Dentro de cada suma, las configuraciones se ordenan primero en el primer contenedor, luego en el segundo, y así sucesivamente.

JAD

3

Jalea , 8 bytes

S0rṗLSÞi

Pruébalo en línea!

Solución de fuerza bruta. El primer caso de prueba es demasiado para TIO, pero lo he verificado localmente en mi computadora portátil. El segundo caso de prueba requiere demasiada RAM, incluso para mi computadora de escritorio.

Cómo funciona

S0rṗLSÞi  Main link. Argument: A (array)

S         Compute the sum s of A.
 0r       Create the range [0, ..., s].
    L     Yield the length l of A.
   ṗ      Cartesian power; yield the array of all l-tuples over [0, ..., s], in
          lexicographical order.
     SÞ   Sort the l-tuples by their sums. The sorting mechanism is stable, so
          l-tuples with the same sum are still ordered lexicographically.
       i  Find the index of A in the generated array of tuples.

Dennis
fuente

Agradable. Su comentario sobre RAM me recordó la fuente de este desafío. Para mi tesis, necesitaba recorrer todas las matrices posibles para algunas bolas a = 8 y lo más alto posible. La idea de transformar las matrices en índices y simplemente recorrerlas surgió exactamente de la limitación de RAM: P

JAD

Es por eso que el código de ejemplo es tan prolijo: P

JAD

1

Clojure, 152 bytes

#(loop[v[(vec(repeat(count %)0))]i 1](if-let[r((zipmap v(range))%)](+ r i)(recur(sort(set(for[v v i(range(count v))](update v i inc))))(+ i(count v)))))

No es tan fácil como pensaba. Versión menos golfizada:

(def f (fn[t](loop[v[(vec(repeat(count t)0))]i 1]
               (if-let[r((zipmap v(range))t)](+ r i)
                 (recur (sort-by (fn[v][(apply + v)v]) (set(for[v v i(range(count v))](update v i inc))))
                        (+ i(count v)))))))

Recorre los estados actuales v, crea un mapa hash a partir de elementos de vsu rango, si se encuentra el estado buscado, se devuelve su rango (+ el número de estados vistos anteriormente). Si no se encuentra, vuelve a aparecer con un nuevo conjunto de estados posibles.

Oh, en realidad no necesitamos esa función de clasificación personalizada ya que todos los estados dentro de cada ciclo tienen una suma idéntica. Esto no es tan lento como esperaba, ya que [3 1 4 1 5 9]solo tardó 2.6 segundos.

NikoNyrh
fuente

1

Mathematica, 50 bytes

Un puerto de Dennis's Jelly responde .

0~Range~Tr@#~Tuples~Length@#~SortBy~Tr~Position~#&

Función sin nombre que toma una lista de enteros como entrada y devuelve una lista de profundidad 2 con un solo entero como salida; por ejemplo, la entrada para el último caso de prueba es {1,0,0,0,0,1}y la salida es {{23}}.

Una versión ungolfed es:

Position[SortBy[Tuples[Range[0,Tr[#]],Length[#]],Tr],#]&

A menudo podemos guardar bytes individuales en Mathematica usando la notación de prefijo (en function@nlugar de function[n]) y la notación de infijo (en a~function~blugar de function[a,b]). Sin embargo, esto solo funciona cuando el código resultante se combina bien con el orden de precedencia intrínseca de Mathematica para aplicar funciones. Yo estaba un poco sorprendido de que aquí, con seis pares de corchetes, que en realidad trabajó para eliminar todo de ellos y guardar seis bytes con el (gratamente) sin soporte de código presentado.

Greg Martin
fuente

Convertir una muestra a un índice