compute all permutation with repetition of list R

Question

i have this list of vector out:

[[1]]
[1] (1,5)(3)(4)(6)

[[2]]
[1] (3,6)(1)(4)(5)

[[3]]
[1] (3,4)(1)(5)(6)

[[4]]
[1] (3,5)(1)(4)(6)

[[5]]
[1] (4,6)(1)(3)(5)

[[5]]
[1] (4,5)(1)(3)(6)

[[6]]
[1] (5,6)(1)(3)(4)

take one elemente for example out[[5]] (4,6)(1)(3)(5), i would generate all permutation of element with all possible order, for example:

{(4,6)(3)(1)(5)},{(3)(4,6)(5)(1)}...

Generally "combination" refers to selecting elements when order doesn't matter, and "permutation" refers to selecting elements when order does matter. So I think you want to generate all *permutations* of a particular list element. — Gregor Thomas, Nov 06 '18 at 21:11
And for that, I'd say [this is a duplicate](https://stackoverflow.com/q/11095992/903061). — Gregor Thomas, Nov 06 '18 at 21:14
I'm guessing the next question will be how to split each element into its components ... and `lapply(l, function(a) Filter(nzchar, strsplit(a, "[()]")[[1]]))` is a sloppy start for that :-) — r2evans, Nov 06 '18 at 21:18
or `lapply(l, function(a) strsplit(gsub("\\(", "", a), ")"))` — r2evans, Nov 06 '18 at 21:24
I'm not sure what the elements of your data structure actually are - they sort of look like Cycle Notation for permutations: https://dlmf.nist.gov/26.13 . Is that what they are? Or are they elements in parentheses just opaque chunks you can shuffle around? Or are the commas functioning as decimal points, like @aliendeg assumed? — Ken Williams, Nov 07 '18 at 15:27
@KenWilliams, I had the same thought. The output looks really similar to what the package `permutations` produces. For example `permutations::allperms(3)` produces `() (23) (12) (123) (132) (13)`. It isn't exactly the same, but it's close. — Joseph Wood, Nov 07 '18 at 16:39
'library(partitions) parts <- listParts(length(x)) out <- rapply(parts, function(ii) x[ii], how="replace")' my datastructure is generate from this code, what i would be do is generate all partitions from a set and fro each partitions compute all permutations — antonio nuzzo, Nov 07 '18 at 16:43
Also, it's interesting that you created that using the `partitions` library and I guessed that you used the `permutations` library. If you look closely at the documentation, `allperms` from `permutations` is simply a wrapper of a function from the `partitions` library. — Joseph Wood, Nov 07 '18 at 16:49
@JosephWood do you think that i can solve my problem in better way? — antonio nuzzo, Nov 07 '18 at 16:55
@antonionuzzo, yes for sure... I'm working on a solution right now that only uses the `partitions` package. — Joseph Wood, Nov 07 '18 at 16:56

Joseph Wood · Accepted Answer · 2018-11-07T17:13:36.230

I think this is what the OP is looking for:

out <- list(c("(1,5)","(3)","(4)","(6)"), c("(3,6)","(1)","(4)","(5)"), 
            c("(3,4)","(1)","(5)","(6)"),c("(3,5)","(1)","(4)","(6)"), 
            c("(4,6)","(1)","(3)","(5)"), c("(4,5)","(1)","(3)","(6)"), 
            c("(5,6)","(1)","(3)","(4)"))

library(RcppAlgos)
myPerms <- lapply(out, function(x) {
    unlist(permuteGeneral(x, length(x), FUN = function(y) {
        paste0(c("{", y, "}"), collapse = "")
    }))
})

We use permuteGeneral from RcppAlgos (I am the author) as we can utilize the FUN argument to pass a custom function that will be applied to each permutation (i.e. paste0(c("{", y, "}"), collapse = "")).

Here is the output of the 5th element:

myPerms[[5]]
[1] "{(4,6)(1)(3)(5)}" "{(4,6)(1)(5)(3)}" "{(4,6)(3)(1)(5)}"
[4] "{(4,6)(3)(5)(1)}" "{(4,6)(5)(1)(3)}" "{(4,6)(5)(3)(1)}"
[7] "{(1)(4,6)(3)(5)}" "{(1)(4,6)(5)(3)}" "{(1)(3)(4,6)(5)}"
[10] "{(1)(3)(5)(4,6)}" "{(1)(5)(4,6)(3)}" "{(1)(5)(3)(4,6)}"
[13] "{(3)(4,6)(1)(5)}" "{(3)(4,6)(5)(1)}" "{(3)(1)(4,6)(5)}"
[16] "{(3)(1)(5)(4,6)}" "{(3)(5)(4,6)(1)}" "{(3)(5)(1)(4,6)}"
[19] "{(5)(4,6)(1)(3)}" "{(5)(4,6)(3)(1)}" "{(5)(1)(4,6)(3)}"
[22] "{(5)(1)(3)(4,6)}" "{(5)(3)(4,6)(1)}" "{(5)(3)(1)(4,6)}"

If you really want permutations with repetition, simply set repetition = TRUE in permuteGeneral. Of course, if you want a more useable output, we can drop the custom FUN altogether.

UPDATE

After learning more about how the OP obtained out above, we can better attack the problem. First we find out that the OP uses listParts from the library partitions. Looking at the source code we have:

listParts
function (x) 
{
    f <- function(pp) {
        out <- split(seq_along(pp), pp)
        class(out) <- c(class(out), "equivalence")
        out
    }
    apply(setparts(x), 2, f)
}
<bytecode: 0x10d7b09f8>
<environment: namespace:partitions>

We can alter this to obtain all permutations:

permListParts <- function (x) 
{
    f <- function(pp) {
        out <- split(seq_along(pp), pp)
        myPerms <- perms(length(out))
        apply(myPerms, 2, function(x) {
            temp <- out[x]
            class(temp) <- c(class(temp), "equivalence")
            temp
        })
    }
    apply(setparts(x), 2, f)
}

We note that we are going against the intent of listParts... quoting the documentation:

"Note that (12)(3)(4) is the same partition as, for example, (3)(4)(21) as the equivalence relation is the same."

Oh well... here is the output for permutations of length 3:

permListParts(3)
[[1]]
[[1]][[1]]
[1] (1,2,3)


[[2]]
[[2]][[1]]
[1] (1,3)(2)

[[2]][[2]]
[1] (2)(1,3)


[[3]]
[[3]][[1]]
[1] (1,2)(3)

[[3]][[2]]
[1] (3)(1,2)


[[4]]
[[4]][[1]]
[1] (2,3)(1)

[[4]][[2]]
[1] (1)(2,3)


[[5]]
[[5]][[1]]
[1] (1)(2)(3)

[[5]][[2]]
[1] (1)(3)(2)

[[5]][[3]]
[1] (2)(1)(3)

[[5]][[4]]
[1] (2)(3)(1)

[[5]][[5]]
[1] (3)(1)(2)

[[5]][[6]]
[1] (3)(2)(1)

Hi, sorry, but with this fuction i had a problem of efficency, because with large vector don't compute all permutations and R crash. I would know if is possibile before compute partitions, then for a partitions of length x (for example [1] (3) (2) (1) length is 3) compute all permutation or caclute permutations only for partitions of length x — antonio nuzzo, Nov 24 '18 at 11:07

score 1 · Answer 2 · answered Nov 06 '18 at 21:06

You could try this:

test <- list(list(1,5),3,4,6)
combn(test,2)
> combn(test,2)
     [,1]   [,2]   [,3]   [,4] [,5] [,6]
[1,] List,2 List,2 List,2 3    3    4   
[2,] 3      4      6      4    6    6

This would give you all the possible combinations of 2 elements from your list. If you want to do that for each element of your main list you can then use a for or lapply on it.

try:

lapply(out, function(x) combn(x,2))

score 1 · Answer 3 · answered Nov 06 '18 at 21:23

1

How about gtools packages

out <- list(
 c(1.5,3,4,6),
 c(3.6,1,4,5),
 c(3.4,1,5,6),
 c(3.5,1,4,6),
 c(4.6,1,3,5),
 c(4.5,1,3,6),
 c(5.6,1,3,4))


require(gtools)

allPerm <- function(x){

  return(permutations(length(x), length(x), x))
}

answered Nov 06 '18 at 21:23

AlienDeg

1,288
1
13
23

compute all permutation with repetition of list R

3 Answers3

UPDATE