12

Nous mettons des boules en un nombre fixe d' un des bacs. Ces poubelles commencent vides.

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

Et un par un, nous ajoutons des balles dans les bacs.

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

Nous avons besoin d'un moyen rapide de parcourir tous les états possibles des bacs, sans doublons et sans en manquer, et nous ne voulons pas énumérer tous les bacs possibles. Donc, à la place, nous attribuons à chaque configuration de bin un index.

Nous attribuons l'index en triant les configurations possibles d'une manière spécifique:

Tri croissant par somme: donc d'abord 0 0 0 0, puis les configurations possibles avec 1 boule ajoutée, puis 2, etc.
Ensuite, triez chaque somme dans l'ordre croissant, du premier au dernier:
```
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
```

L'index est ensuite attribué croissant dans cette liste:

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

Règles

Créez une fonction ou un programme qui prend une liste de n'importe quelle taille avec des entiers non négatifs et affiche ou affiche son index. Vous pouvez supposer que a vaut au moins 2. Le code le plus court l'emporte. Vous pouvez utiliser une sortie indexée 0 ou indexée 1, mais spécifiez celle que vous utilisez. NB: tous les exemples ici sont indexés 1.

Exemple de code

Non 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)
}

Cas de test

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
la source

Comment fonctionne le tri via la valeur numérique de la concaténation lorsque les nombres ont différents nombres de chiffres?

TheBikingViking

@TheBikingViking hmm, n'y avais pas pensé, j'ai changé le libellé pour refléter l'exemple de code et les cas de test. Au sein de chaque somme, les configurations sont triées d'abord dans le premier bac, puis dans le second, etc.

JAD

3

Gelée , 8 octets

S0rṗLSÞi

Essayez-le en ligne!

Solution de force brute. Le premier cas de test est trop pour TIO, mais je l'ai vérifié localement sur mon ordinateur portable. Le deuxième cas de test nécessite trop de RAM, même pour mon ordinateur de bureau.

Comment ça fonctionne

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
la source

Agréable. Votre remarque sur la RAM m'a rappelé la source de ce défi. Pour ma thèse, j'avais besoin de boucler sur tous les tableaux possibles pour certains a = 8 et aussi haut que possible balles. L'idée de transformer les tableaux en indices et de les boucler vient exactement de la limitation de la RAM: P

JAD

C'est aussi pourquoi l'exemple de code est si verbeux: P

JAD

1

Clojure, 152 octets

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

Pas aussi facile que je le pensais. Version moins golfée:

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

Boucle sur les états actuels v, crée une carte de hachage des éléments de và leur rang, si l'état recherché est trouvé, son rang est renvoyé (+ le nombre d'états précédemment vus). S'il n'est pas trouvé, il revient avec un nouvel ensemble d'états possibles.

Oh en fait, nous n'avons pas besoin de cette fonction de tri personnalisée car tous les états de chaque boucle ont une somme identique. Ce n'est pas aussi lent que prévu car cela [3 1 4 1 5 9]n'a pris que 2,6 secondes.

NikoNyrh
la source

1

Mathematica, 50 octets

Un port de Dennis's Jelly répond .

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

Fonction sans nom prenant une liste d'entiers en entrée et renvoyant une liste de profondeur 2 avec un seul entier en sortie; par exemple, l'entrée pour le dernier scénario de test est {1,0,0,0,0,1}et la sortie est {{23}}.

Une version légèrement non golfée est:

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

Souvent, nous pouvons enregistrer des octets individuels dans Mathematica en utilisant la notation préfixe ( function@nau lieu de function[n]) et la notation infixe ( a~function~bau lieu de function[a,b]). Cela ne fonctionne cependant que lorsque le code résultant correspond bien à l'ordre de priorité intrinsèque de Mathematica pour l'application des fonctions. J'ai été un peu étonné ici que, avec six jeux de crochets, cela ait réellement fonctionné pour les supprimer tous et économiser six octets avec le code soumis (agréablement sans crochets).

Greg Martin
la source

Convertir un échantillon en index