3

Say I have 3 green balls, 2 orange balls, and 8 yellow balls. I want to order them, how can I generate all possible sequences given that all balls of the same color are identical.

In R, using gregmisc, I could do 

balls<-c('orange','orange', 'green', 'green','green','yellow'...'yellow')

and then just do 

g <- permutations(length(balls),length(balls),v=balls,set=F)
g.reduced <- g[!duplicated(g),]

But that seems very unnecessary.

JoshDG
  • 3,871
  • 10
  • 51
  • 85
  • If your color vector is v, just do `g <- unique(permutations(length(v),length(v),v,F))`. One-liner. – jclancy Aug 23 '12 at 08:12
  • Definitely more readable, but, that still doesn't get rid of the extra computational work to calculate the duplicates. As length(v) gets bigger that may not be feasible. – JoshDG Aug 23 '12 at 13:13
  • Alright, how about this algorithm. I'll assume just one repeated element for simplicity, but I don't think it generalizing it will be a problem. `unique` everything in the first place, then calculate the permutations. You get out a matrix with the permutations of your other elements and one of the previously-not-unique elements. Expand each row to a vector of length `m + 1 + n - 1` where n is the number of previously-not-unique elements and m is the number of other elements. Starting m + 1 elements from the end, place the first element in your original row and run through all the possible – jclancy Aug 23 '12 at 13:23
  • spacings of the elements in the original row, filling in the `n - 1` other elements in between. The idea is that the permutation matrix gives an ordering and you fill in the potential blanks with your `n - 1` repeated elements. I'll try to code or pseudocode this up and place it in an answer. – jclancy Aug 23 '12 at 13:24
  • 2
    This may be the same question as here: Permute all unique enumerations of a vector in R: http://stackoverflow.com/q/5671149/210673 – Aaron left Stack Overflow Aug 23 '12 at 14:24

1 Answers1

0

This is the most obvious way I can think of to do this. This is my approach from the comments above, but I eliminated all entries of the nonunique element from the vector instead of all but one. If I had left one in, this method would have resulted in one duplicate of every entry.

arr  # one of the rows of the matrix of permutations
l  # the length of the original un-unique'd vector
out <- list()
vec <- vector(length=l)
find.placings <- function(start, pos, vec, m) {
    if (m == 0)
        return(vec)
    for (i in pos:(l - m + 1)) {
        vec[i] <- arr[start]
        out[[length(out) + 1]] <- find.placings(start + 1, i + 1, vec, m - 1)
    }
}

Of course as this is highly recursive beware. I haven't tested it either. If you want to call the function, give it original values of (1, 1, vector(length=l), m).

jclancy
  • 49,598
  • 5
  • 30
  • 34
  • I don't understand how to use this code; what is the equivalent of the `balls` object in the original post? – Aaron left Stack Overflow Aug 23 '12 at 16:52
  • Again, assuming the `balls` vector only has one entry with duplicates (the code would be more complex for more duplicate entries), you delete those entries, leaving none. Save the length of the original vector as 'l'. You then call `permutations` on that new vector, obtaining the matrix `m`. On each row `arr` of `m`, you call the above code, which will give you all the orderings of the elements of `arr` with spaces in between. It's a simple matter to fill those spaces (`NA`'s, most likely) with the original duplicated element. – jclancy Aug 24 '12 at 06:21