Fonction R pour créer des permutations monotones (croissantes ou décroissantes) [dupliquer]
J'essaie de créer une fonction efficace pour générer toutes les permutations monotones croissantes d'un grand vecteur. Évidemment, réduire les sorties de expand.grid
ou gtools::permutations
fonctionne, mais uniquement pour les petits vecteurs.
Exemple:
x = 1:3
Sortie désirée:
1, 1, 1
1, 1, 2
1, 1, 3
1, 2, 2
1, 2, 3
1, 3, 3
2, 2, 2
2, 2, 3
2, 3, 3
3, 3, 3
Des suggestions utilisant la base R ou des packages existants avec cette capacité?
EDIT: Une solution idéale éviterait de générer l'ensemble complet de permutations pour ensuite sous-ensemble.
Réponses
Son utilisation data.table
est assez simple:
expand.monotonic <- function(x, len=length(x)){
do.call(CJ, lapply(integer(len), function(...) x ))[
eval(parse(text=paste0("V", 2:len, ">=", "V", 1:(len-1), collapse="&") )), ]
}
expand.monotonic(1:3)
V1 V2 V3
1: 1 1 1
2: 1 1 2
3: 1 1 3
4: 1 2 2
5: 1 2 3
6: 1 3 3
7: 2 2 2
8: 2 2 3
9: 2 3 3
10: 3 3 3
explication:
Commencez par créer une liste contenant les len
temps vectoriels répliqués , utilisez data.table::CJ
pour croiser tous les vecteurs. Et c'est là que la magie se produit en fonction de la len
création d'une expression, tout V2>=V1&V3>=V2
comme V#
le nom par défaut des colonnes sans nom et du sous-ensemble du résultat de l'évaluation de ladite expression.
parse(text=paste0("V", 2:len, ">=", "V", 1:(len-1), collapse="&") )
# expression(V2>=V1&V3>=V2)
Voici un code qui crée des permutations avec des répétitions autorisées comme dans votre exemple, et détecte si chaque permutation est monotone
x <- 1:3
# Generate permutations of length x
out <- gtools::permutations(length(x), length(x), v = x, repeats.allowed=TRUE)
# Detect if they're monotonic
mono <- apply(out, 1, function(x) { all(x == cummax(x)) })
output_with_monotonic_label <- cbind(out, mono)
# output_with_monotonic_label
# mono
# [1,] 1 1 1 1
# [2,] 1 1 2 1
# [3,] 1 1 3 1
# [4,] 1 2 1 0
# [5,] 1 2 2 1
# [6,] 1 2 3 1
# [7,] 1 3 1 0
# [8,] 1 3 2 0
# [9,] 1 3 3 1
# [10,] 2 1 1 0
# ....