search

RobinHankin / partitions

R package for integer partitions
9 stars 5 forks source link

Permutations of a multiset #1

Closed sarahemarshall closed 5 years ago

sarahemarshall commented 6 years ago

Is it possible to obtain all permutations of a multiset using this package? For example, all permutations of the word "PEPPER".

RobinHankin commented 6 years ago

hello, thanks for this. That functionality does not exist in the package, but it would be reasonable to expect it to be there. The best I can do is as follows:

(apply(matrix(c("p","e","r")[unique(t(matrix(c(1,1,1,2,2,3)[perms(6)],nrow=6)))],ncol=6),1,paste,collapse=""))

but this is terribly inefficient because it evaluates all 6!=720 permutations of {1,2,3,4,5,6} and then weeds out duplicates ("pepper" itself appears as element 13).

I'll add it to my list of things-to-do, but it may take me some time to finish....

RobinHankin commented 6 years ago

Knuth's algorithm L at the start of fasc2b would work here.

RobinHankin commented 5 years ago

for convenience, here is the output of the command above:

> (apply(matrix(c("p","e","r")[unique(t(matrix(c(1,1,1,2,2,3)[perms(6)],nrow=6)))],ncol=6),1,paste,collapse=""))
 [1] "pppeer" "pppere" "pppree" "ppeper" "ppepre" "ppeepr" "ppeerp" "pperpe"
 [9] "pperep" "pprpee" "pprepe" "ppreep" "pepper" "peppre" "pepepr" "peperp"
[17] "peprpe" "peprep" "peeppr" "peeprp" "peerpp" "perppe" "perpep" "perepp"
[25] "prppee" "prpepe" "prpeep" "preppe" "prepep" "preepp" "eppper" "epppre"
[33] "eppepr" "epperp" "epprpe" "epprep" "epeppr" "epeprp" "eperpp" "eprppe"
[41] "eprpep" "eprepp" "eepppr" "eepprp" "eeprpp" "eerppp" "erpppe" "erppep"
[49] "erpepp" "ereppp" "rpppee" "rppepe" "rppeep" "rpeppe" "rpepep" "rpeepp"
[57] "repppe" "reppep" "repepp" "reeppp"
>
RobinHankin commented 5 years ago

With multiset() we can enumerate the permutations of the word "pepper" as requested without the inefficiencies of the previous solution:

library("partitions")
library("magrittr")
string <- "pepper"

string               %>%
  strsplit("")        %>%
  `[[`(1)              %>%
  match(letters)        %>%
  multiset               %>%
  `[`(letters,.)          %>%
matrix(nrow=nchar(string)) %>%
apply(2,paste,collapse="")

And we get

 [1] "eepppr" "eepprp" "eeprpp" "eerppp" "epeppr" "epeprp" "eperpp" "eppepr"
 [9] "epperp" "eppper" "epppre" "epprep" "epprpe" "eprepp" "eprpep" "eprppe"
[17] "ereppp" "erpepp" "erppep" "erpppe" "peeppr" "peeprp" "peerpp" "pepepr"
[25] "peperp" "pepper" "peppre" "peprep" "peprpe" "perepp" "perpep" "perppe"
[33] "ppeepr" "ppeerp" "ppeper" "ppepre" "pperep" "pperpe" "pppeer" "pppere"
[41] "pppree" "ppreep" "pprepe" "pprpee" "preepp" "prepep" "preppe" "prpeep"
[49] "prpepe" "prppee" "reeppp" "repepp" "reppep" "repppe" "rpeepp" "rpepep"
[57] "rpeppe" "rppeep" "rppepe" "rpppee"
RobinHankin commented 5 years ago

See https://github.com/RobinHankin/freealg/issues/10 for an application of this.

RobinHankin commented 5 years ago

See also issue #10