12

Estamos colocando bolas em um número fixo de caixas. Essas caixas começam vazias.

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

E um por um, adicionamos bolas às caixas.

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

Precisamos de uma maneira rápida de percorrer todos os estados possíveis das caixas, sem duplicatas e sem perder nenhuma, e não queremos enumerar todas as caixas possíveis. Então, em vez disso, atribuímos a cada configuração de compartimento um índice.

Atribuímos o índice classificando as configurações possíveis de uma maneira específica:

Classifique em ordem crescente por soma: primeiro 0 0 0 0, as configurações possíveis com 1 bola adicionada e depois 2, etc.
Em seguida, classifique dentro de cada soma em ordem crescente, do primeiro compartimento ao ú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
```

O índice é então atribuído ascendente através desta 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

Regras

Crie uma função ou programa que obtenha uma lista de qualquer tamanho com números inteiros não negativos e imprima ou produza seu índice. Você pode assumir a ser pelo menos 2. vitórias código mais curto. Você pode usar saída indexada em 0 ou indexada em 1, mas especifique qual você usa. NB: todos os exemplos aqui são 1 indexados.

Código de exemplo

Não jogou golfe, em 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 teste

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
fonte

Como funciona a classificação pelo valor numérico da concatenação quando as contagens têm números diferentes de dígitos?

TheBikingViking

@TheBikingViking hmm, não tinha pensado nisso, mudei a redação para refletir o código de exemplo e os casos de teste. Dentro de cada soma, as configurações são classificadas primeiro na primeira posição, depois na segunda e assim por diante.

JAD

3

Geléia , 8 bytes

S0rṗLSÞi

Experimente online!

Solução de força bruta. O primeiro caso de teste é demais para o TIO, mas eu o verifiquei localmente no meu laptop. O segundo caso de teste requer muita RAM, mesmo para o meu computador desktop.

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

Agradável. Sua observação sobre a RAM me lembrou a fonte desse desafio. Para minha tese, eu precisava percorrer todas as matrizes possíveis por algumas bolas = 8 e o mais alto possível. A idéia de transformar os arrays em índices e apenas fazer um loop sobre eles veio exatamente da limitação da RAM: P

JAD

É também por isso que o código de exemplo é tão prolixo: 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)))))

Não é tão fácil quanto eu pensava. Versão menos golfe:

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

Loops sobre estados atuais v, cria um mapa de hash a partir de elementos de vsua classificação, se o estado pesquisado for encontrado, sua classificação será retornada (+ o número de estados vistos anteriormente). Se não for encontrado, ele retornará com um novo conjunto de estados possíveis.

Na verdade, não precisamos dessa função de classificação personalizada, pois todos os estados em cada loop têm soma idêntica. Isso não é tão lento quanto eu esperava, pois [3 1 4 1 5 9]levou apenas 2,6 segundos.

NikoNyrh
fonte

1

Mathematica, 50 bytes

Um porto da resposta da geléia de Dennis .

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

Função sem nome, recebendo uma lista de números inteiros como entrada e retornando uma lista de profundidade 2 com um único número inteiro como saída; por exemplo, a entrada para o último caso de teste é {1,0,0,0,0,1}e a saída é {{23}}.

Uma versão ligeiramente não-destruída é:

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

Frequentemente, podemos salvar bytes individuais no Mathematica usando notação de prefixo (em function@nvez de function[n]) e notação de infixo (em a~function~bvez de function[a,b]). No entanto, isso só funciona quando o código resultante se encaixa bem na ordem de precedência intrínseca do Mathematica para a aplicação de funções. Fiquei meio surpreso aqui que, com seis conjuntos de colchetes, ele realmente trabalhou para remover todos eles e salvar seis bytes com o código enviado (agradavelmente sem colchetes).

Greg Martin
fonte

Converter uma amostra em um índice