Une autre question sur la mise en œuvre la plus élégante et la plus simple des combinaisons d'éléments dans F #.
Il doit renvoyer toutes les combinaisons d'éléments d'entrée (liste ou séquence). Premier argument est le nombre d'éléments dans une combinaison.
par exemple:
8 Réponses :
let rec comb n l =
match (n,l) with
| (0,_) -> [[]]
| (_,[]) -> []
| (n,x::xs) ->
let useX = List.map (fun l -> x::l) (comb (n-1) xs)
let noX = comb n xs
useX @ noX
La solution la plus rapide jusqu'à présent, mais moins concise.
Il a l'air très moche dans c #. Public statique iEnumerable
Il y a plus de version concise de la réponse de KVB:
let rec comb n l =
match (n,l) with
| (0,_) -> [[]]
| (_,[]) -> []
| (n,x::xs) ->
List.flatten [(List.map (fun l -> x::l) (comb (n-1) xs)); (comb n xs)]
Ma solution est moins concise, moins efficace (ALTHO, pas de récursivité directe utilisée), mais elle renvoie Trullly toutes les combinaisons (actuellement seulement des paires, doivent étendre le filtre de sorte qu'il peut renvoyer une tuple de deux listes, fera peu plus tard). peigne [1; 2; 3; 4] retournera:
[[1; 2]; [1; 3]; [1; 4]; [2; 1]; [2; 3]; [2; 4]; [3; 1]; [3; 2]; [3; 4]; [4; 1]; [4; 2]; [4; 3]]
Cette solution ne fonctionne pas correctement. Cela ne renvoie pas les combinaisons, mais seulement des paires d'éléments.
Ce sont toutes des combinaisons possibles. Pas seulement des combinaisons de queue. peigne [1; 2; 3] est ajouté à chacun de [2; 3], 2 ajouté à chacun de [1; 3], 3 ajouté à chacun de [1; 2]
> peigne 3 [1..4] ;; VAL IT: INT LISTE LISTE = [[1; 2; 3]; [1; 2; 4]; [1; 3; 4]; [2; 3; 4]] Avec plus d'éléments, il ne devrait pas retourner des paires, mais triple (pour n = 3)
une solution moins concise et plus rapide que SSP:
Quelqu'un pourrait-il écrire plus simple que cette solution?
OK, juste des combinaisons de queue peu d'approche différente (sans utilisation de la fonction de bibliothèque)
La réponse acceptée est magnifique et compréhensible rapidement si vous connaissez la récursion de l'arbre. Étant donné que l'élégance était recherchée, l'ouverture de ce long fil dormant semble quelque peu inutile.
Cependant, une solution plus simple a été demandée. Les algorithmes itératifs semblent parfois plus simples pour moi. En outre, la performance a été mentionnée comme un indicateur de qualité et les processus itératifs sont parfois plus rapides que les personnes récursives.
Le code suivant est récursif et génère un processus itératif. Il nécessite un tiers de la quantité de temps pour calculer des combinaisons de taille 12 à partir d'une liste d'éléments de 24 éléments. L'idée qui permet un processus itératif est de pré-calculer une Carte du dernier élément choisi vers une liste des éléments disponibles restants. Cette carte est stockée dans Le code n'est pas concis, il n'est pas conforme au compteur lyrique et à la rime. RestderAfter .
A Implémentation naïf em> à l'aide d'une expression de séquence. Personnellement, je pense souvent que les expressions de séquence sont plus faciles à suivre que d'autres fonctions plus denses. let combinations (k : int) (xs : 'a list) : ('a list) seq =
let rec loop (k : int) (xs : 'a list) : ('a list) seq = seq {
match xs with
| [] -> ()
| xs when k = 1 -> for x in xs do yield [x]
| x::xs ->
let k' = k - 1
for ys in loop k' xs do
yield x :: ys
yield! loop k xs }
loop k xs
|> Seq.filter (List.length >> (=)k)
méthode prise de mathématiques discrètes et ses applications em>.
Le résultat renvoie une liste ordonnée de combinaisons stockées dans des tableaux.
Et l'index est basé sur 1. let permutationA (currentSeq: int []) (n:int) (r:int): Unit =
let mutable i = r
while currentSeq.[i - 1] = n - r + i do
i <- (i - 1)
currentSeq.[i - 1] <- currentSeq.[i - 1] + 1
for j = i + 1 to r do
currentSeq.[j - 1] <- currentSeq.[i - 1] + j - i
()
let permutationNum (n:int) (r:int): int [] list =
if n >= r then
let endSeq = [|(n-r+1) .. n|]
let currentSeq: int [] = [|1 .. r|]
let mutable resultSet: int [] list = [Array.copy currentSeq];
while currentSeq <> endSeq do
permutationA currentSeq n r
resultSet <- (Array.copy currentSeq) :: resultSet
resultSet
else
[]
Question vaguement liée: Stackoverflow.com/Questions/286427/...