Étant donné n, génère toutes les permutations de taille inférieure à 0,5n

Jan 08 2021

Étant donné un nombre entier n, je voudrais générer dans un vecteur, aussi efficacement que possible, toutes les permutations d'entiers de taille inférieure ou égale à 0.5n.

Par exemple pour n=7cela serait:

15-element Array{Array{Int64,1},1}:
 [1]
 [2]
 [3]
 [1, 2]
 [1, 3]
 [2, 1]
 [2, 3]
 [3, 1]
 [3, 2]
 [1, 2, 3]
 [1, 3, 2]
 [2, 1, 3]
 [2, 3, 1]
 [3, 1, 2]
 [3, 2, 1]

Mon idée actuelle est de générer toutes les permutations de taille kinférieure 0.5net de les ajouter:

using Combinatorics

function generate_half_perm(n)
    half_n = floor(Int, n/2)
    result = []
    for l in 1:half_n
            for c in permutations(1:half_n, l)
                    push!(result, c)
            end
    end
    return result
end

generate_half_perm (7) donne alors la première instance de ce message. Je pense que ce code est actuellement au- dessus O(2^(n/2).n)qui est la complexité du code sans celui nécessaire pour générer les combinaisons, combinations(1:half_n, l).

Je me demandais s'il y avait une meilleure idée qui pourrait conduire à un code plus rapide étant donné que mon n sera probablement supérieur à 100.

J'ai eu l'idée d'utiliser ce code [Méthode optimale pour calculer les permutations dans Julia] mais la fonction de production est obsolète et devrait être remplacée selon cette autre réponse [Comment remplacer consommer et produire avec des canaux] et maintenant cela commence à devenir compliqué pour moi comprendre!

Si vous avez une meilleure idée algorithmiquement, sans l'implémentation Julia, je serai heureux de l'essayer :)

petite retouche: je me rends compte que ce que je voulais c'était:

collect(Iterators.flatten(permutations.(powerset(1:7,0, floor(Int, 7/2)))))

Merci à @Przemyslaw Szufel de m'avoir permis de le trouver :)

Réponses

3 PrzemyslawSzufel Jan 08 2021 at 19:21

Pour votre valeur "la moitié de N" égale à 3, ce serait:

using Combinatorics
Iterators.flatten(permutations.(powerset(1:3,1)))

Notez que ce n'est pas alloué, donc si vous voulez voir le résultat collectest requis:

julia> collect(Iterators.flatten(permutations.(powerset(1:3,1))))
15-element Array{Array{Int64,1},1}:
 [1]
 [2]
 [3]
 [1, 2]
 [2, 1]
 [1, 3]
 [3, 1]
 [2, 3]
 [3, 2]
 [1, 2, 3]
 [1, 3, 2]
 [2, 1, 3]
 [2, 3, 1]
 [3, 1, 2]
 [3, 2, 1]