5

I am trying to find a way to get a list in R of all the possible unique permutations of A,A,A,A,B,B,B,B,B.

Combinations was what was originally thought to be the method for obtaining a solution, hence the combinations answers.

HazelnutCoffee
  • 175
  • 1
  • 1
  • 9
  • perhaps `?combn` is what you are after? – Chase May 28 '11 at 22:12
  • good start but the combn function requires you to choose m at a time. I just was looking for all the unique combinations of the above string......not a subset. Perhaps I am not thinking about this right either. – HazelnutCoffee May 28 '11 at 22:27
  • 1
    You might try both `?unique` and `?combn`. – bill_080 May 28 '11 at 22:35
  • Gotcha. Question for ya - still thinking in the combn mindset, are the values returned by `combn(x, 2)` that are all `A A` considered redundant? – Chase May 28 '11 at 22:40
  • Is this the same as [Permute all unique enumerations of a vector in R](http://stackoverflow.com/questions/5671149/permute-all-unique-enumerations-of-a-vector-in-r)? – Joshua Ulrich May 29 '11 at 00:07
  • Seems to be the same to me, though it's quite a bit simpler because there are only two possible values in the example. – Aaron left Stack Overflow May 30 '11 at 02:39

2 Answers2

3

I think this is what you're after. @bill was on the ball with the recommendation of combining unique and combn. We'll also use the apply family to generate ALL of the combinations. Since unique removes duplicate rows, we need to transpose the results from combn before uniqueing them. We then transpose them back before returning to the screen so that each column represents a unique answer.

#Daters
x <- c(rep("A", 4), rep("B",5))
#Generates a list with ALL of the combinations
zz <- sapply(seq_along(x), function(y) combn(x,y))
#Filter out all the duplicates
sapply(zz, function(z) t(unique(t(z))))

Which returns:

[[1]]
     [,1] [,2]
[1,] "A"  "B" 

[[2]]
     [,1] [,2] [,3]
[1,] "A"  "A"  "B" 
[2,] "A"  "B"  "B" 

[[3]]
     [,1] [,2] [,3] [,4]
[1,] "A"  "A"  "A"  "B" 
[2,] "A"  "A"  "B"  "B" 
[3,] "A"  "B"  "B"  "B" 

...

EDIT Since the question is about permuations and not combinations, the answer above is not that useful. This post outlines a function to generate the unique permutations given a set of parameters. I have no idea if it could be improved upon, but here's one approach using that function:

fn_perm_list <-
 function (n, r, v = 1:n)
 {
    if (r == 1)
       matrix(v, n, 1)
    else if (n == 1)
       matrix(v, 1, r)
    else {
       X <- NULL
       for (i in 1:n) X <- rbind(X, cbind(v[i], fn_perm_list(n -
            1, r - 1, v[-i])))
        X
    }
 } 

zz <- fn_perm_list(9, 9)

#Turn into character matrix. This currently does not generalize well, but gets the job done
zz <- ifelse(zz <= 4, "A", "B")

#Returns 126 rows as indicated in comments
unique(zz)
Chase
  • 67,710
  • 18
  • 144
  • 161
  • What I have really done here is mistaken permutation with combination. Order in this case matters and in that situation i believe there are 9!/(4!*5!) = 126 different permutations of AAAABBBBB. Some examples of the permuations would be: AAABBBBBA , AAABBBBAB , AAAABBBABB , AAAABBABBB , and so on –. Could we modify that code Chase to get us there? – HazelnutCoffee May 28 '11 at 23:12
  • @RyanB - updated answer to address your comment. There appears to be some good information in the link I referenced which may be more efficient than the function I grabbed. – Chase May 28 '11 at 23:17
  • @RyanB - you can also update your question with this information and the title as well. – Chase May 28 '11 at 23:30
  • @RyanB: If Chase nailed it, please select his answer so that it is easier for others to see that. – Iterator Aug 05 '11 at 19:47
2

There's no need to generate permutations and then pick out the unique ones. Here's a much simpler way (and much, much faster as well): To generate all permutations of 4 A's and 5 B's, we just need to enumerate all possible ways of placing 4 A's among 9 possible locations. This is simply a combinations problem. Here's how we can do this:

x <- rep('B',9) # vector of 9 B's

a_pos <- combn(9,4) # all possible ways to place 4 A's among 9 positions

perms <- apply(a_pos, 2, function(p) replace(x,p,'A')) # all desired permutations

Each column of the 9x126 matrix perms is a unique permutation 4 A's and 5 B's:

> dim(perms)
[1]   9 126
> perms[,1:4] ## look at first few columns
      [,1] [,2] [,3] [,4]
 [1,] "A"  "A"  "A"  "A" 
 [2,] "A"  "A"  "A"  "A" 
 [3,] "A"  "A"  "A"  "A" 
 [4,] "A"  "B"  "B"  "B" 
 [5,] "B"  "A"  "B"  "B" 
 [6,] "B"  "B"  "A"  "B" 
 [7,] "B"  "B"  "B"  "A" 
 [8,] "B"  "B"  "B"  "B" 
 [9,] "B"  "B"  "B"  "B" 
Prasad Chalasani
  • 19,912
  • 7
  • 51
  • 73