Generating Permutations with Repetitions

Generating permutations with repetitions

You are looking for the Cartesian Product.

In mathematics, a Cartesian product (or product set) is the direct product of two sets.

In your case, this would be {1, 2, 3, 4, 5, 6} x {1, 2, 3, 4, 5, 6}.
itertools can help you there:

import itertools
x = [1, 2, 3, 4, 5, 6]
[p for p in itertools.product(x, repeat=2)]
[(1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (1, 6), (2, 1), (2, 2), (2, 3), 
 (2, 4), (2, 5), (2, 6), (3, 1), (3, 2), (3, 3), (3, 4), (3, 5), (3, 6), 
 (4, 1), (4, 2), (4, 3), (4, 4), (4, 5), (4, 6), (5, 1), (5, 2), (5, 3), 
 (5, 4), (5, 5), (5, 6), (6, 1), (6, 2), (6, 3), (6, 4), (6, 5), (6, 6)]

To get a random dice roll (in a totally inefficient way):

import random
random.choice([p for p in itertools.product(x, repeat=2)])
(6, 3)

How to generate all permutations with repetitions /make x amount of nested for functions

ListA = [0, 1, 2, 3]
n = 3

def func(ListA, n):
    res = [[l] for l in ListA]
    for i in range(n-1):
        res = [r+[l] for r in res for l in ListA]
    return res

res_Michael = func(ListA, n)

res = []
for i in ListA:
    for x in ListA:
        for y in ListA:
            res.append([i, x, y])

print(res_Michael == res)
# True

---

res = [[l] for l in ListA]

Make init list like:

[[0], [1], [2], [3]]

We need iter the elems, and concat it later:

[   [0, 0], ..., [0, 3], 
    [1, 0], ..., [1, 3], ...
]

for i in range(n-1):

Because res had been inited, so we concat only (n-1) times

res = [r+[l] for r in res for l in ListA]

r+[l]

type of r is list

r+[l] means concat list r and [l]

l is a number in ListA,

so

[l]

is a list with only one element

for r in res for l in ListA

Your output is:

[0, 0, 0] then [0, 0, 1]

not:

[0, 0, 0] then [1, 0, 0]

so if wont be for l in ListA for r in res

---

thats all

Python permutations with repetitions

import itertools
x = ['a', 'b', 'c']
print([''.join(p) for p in itertools.product(x, repeat=3)])

Will produce:

['aaa', 'aab', 'aac', 'aba', 'abb', 'abc', 'aca', 'acb', 'acc', 'baa', 'bab', 'bac', 'bba', 'bbb', 'bbc', 'bca', 'bcb', 'bcc', 'caa', 'cab', 'cac', 'cba', 'cbb', 'cbc', 'cca', 'ccb', 'ccc']

Print all permutations with repetition of characters in r?

One option would be to use the RcppAlgos package although there are at least a handful of other packages that have functions for this:

library(RcppAlgos)

res <- permuteGeneral(LETTERS[1:4], 4, TRUE)

head(res)

     [,1] [,2] [,3] [,4]
[1,] "A"  "A"  "A"  "A" 
[2,] "A"  "A"  "A"  "B" 
[3,] "A"  "A"  "A"  "C" 
[4,] "A"  "A"  "A"  "D" 
[5,] "A"  "A"  "B"  "A" 
[6,] "A"  "A"  "B"  "B" 

nrow(res)
[1] 256

Generate permutations of list with repeated elements

This web page looks promising.

def next_permutation(seq, pred=cmp):
    """Like C++ std::next_permutation() but implemented as
    generator. Yields copies of seq."""
    def reverse(seq, start, end):
        # seq = seq[:start] + reversed(seq[start:end]) + \
        #       seq[end:]
        end -= 1
        if end <= start:
            return
        while True:
            seq[start], seq[end] = seq[end], seq[start]
            if start == end or start+1 == end:
                return
            start += 1
            end -= 1
    if not seq:
        raise StopIteration
    try:
        seq[0]
    except TypeError:
        raise TypeError("seq must allow random access.")
    first = 0
    last = len(seq)
    seq = seq[:]
    # Yield input sequence as the STL version is often
    # used inside do {} while.
    yield seq[:]
    if last == 1:
        raise StopIteration
    while True:
        next = last - 1
        while True:
            # Step 1.
            next1 = next
            next -= 1
            if pred(seq[next], seq[next1]) < 0:
                # Step 2.
                mid = last - 1
                while not (pred(seq[next], seq[mid]) < 0):
                    mid -= 1
                seq[next], seq[mid] = seq[mid], seq[next]
                # Step 3.
                reverse(seq, next1, last)
                # Change to yield references to get rid of
                # (at worst) |seq|! copy operations.
                yield seq[:]
                break
            if next == first:
                raise StopIteration
    raise StopIteration

>>> for p in next_permutation([int(c) for c in "111222"]):
...     print p
... 
[1, 1, 1, 2, 2, 2]
[1, 1, 2, 1, 2, 2]
[1, 1, 2, 2, 1, 2]
[1, 1, 2, 2, 2, 1]
[1, 2, 1, 1, 2, 2]
[1, 2, 1, 2, 1, 2]
[1, 2, 1, 2, 2, 1]
[1, 2, 2, 1, 1, 2]
[1, 2, 2, 1, 2, 1]
[1, 2, 2, 2, 1, 1]
[2, 1, 1, 1, 2, 2]
[2, 1, 1, 2, 1, 2]
[2, 1, 1, 2, 2, 1]
[2, 1, 2, 1, 1, 2]
[2, 1, 2, 1, 2, 1]
[2, 1, 2, 2, 1, 1]
[2, 2, 1, 1, 1, 2]
[2, 2, 1, 1, 2, 1]
[2, 2, 1, 2, 1, 1]
[2, 2, 2, 1, 1, 1]
>>> 

---

2017-08-12

Seven years later, here is a better algorithm (better for clarity):

from itertools import permutations

def unique_perms(series):
    return {"".join(p) for p in permutations(series)}

print(sorted(unique_perms('1122')))

Get different sets of numbers with repetition

This should work... Using the permutations function from itertools and making a set out of everything to prevent duplicates from being added to the overall result

In [20]: from itertools import permutations                                     

In [21]: a = [1, 1, 2, 3]                                                       

In [22]: all_results = set()                                                    

In [23]: for i in range(1, len(a)): 
    ...:     all_results.update(set(permutations(a, i))) 
    ...:                                                                        

In [24]: all_results                                                            
Out[24]: 
{(1,),
 (1, 1),
 (1, 1, 2),
 (1, 1, 3),
 (1, 2),
 (1, 2, 1),
 (1, 2, 3),
 (1, 3),
 (1, 3, 1),
 (1, 3, 2),
 (2,),
 (2, 1),
 (2, 1, 1),
 (2, 1, 3),
 (2, 3),
 (2, 3, 1),
 (3,),
 (3, 1),
 (3, 1, 1),
 (3, 1, 2),
 (3, 2),
 (3, 2, 1)}

In [25]:       

                                                             

Generate permutations of specific length with repetition in R?

There are several packages that will produce exactly what you need. Let's start with the classic gtools. Also, from the looks of the example provided by the OP, we are looking for permutations without repetition, not combinations with repetition.

wordsList <- c("alice", "moon", "walks", "mars", "sings", "guitar", "bravo")

library(gtools)
attempt1 <- permutations(length(wordsList), 3, wordsList)
head(attempt1)
        [,1]    [,2]     [,3]    
[1,] "alice" "bravo"  "guitar"
[2,] "alice" "bravo"  "mars"  
[3,] "alice" "bravo"  "moon"  
[4,] "alice" "bravo"  "sings" 
[5,] "alice" "bravo"  "walks" 
[6,] "alice" "guitar" "bravo"

Then there is iterpc.

library(iterpc)
attempt2 <- getall(iterpc(length(wordsList), 3, labels = wordsList, ordered = TRUE))
head(attempt2)
        [,1]    [,2]    [,3]    
[1,] "alice" "moon"  "walks" 
[2,] "alice" "moon"  "mars"  
[3,] "alice" "moon"  "sings" 
[4,] "alice" "moon"  "guitar"
[5,] "alice" "moon"  "bravo" 
[6,] "alice" "walks" "moon"

And finally, RcppAlgos (which I am the author of)

library(RcppAlgos)
attempt3 <- permuteGeneral(wordsList, 3)
head(attempt3)
        [,1]     [,2]     [,3]    
[1,] "alice"  "bravo"  "guitar"
[2,] "bravo"  "alice"  "guitar"
[3,] "guitar" "alice"  "bravo" 
[4,] "alice"  "guitar" "bravo" 
[5,] "bravo"  "guitar" "alice" 
[6,] "guitar" "bravo"  "alice"

They are all fairly efficient and produce similar outcomes (different orderings)

identical(attempt1[do.call(order,as.data.frame(attempt1)),],
          attempt3[do.call(order,as.data.frame(attempt3)),])
[1] TRUE

identical(attempt1[do.call(order,as.data.frame(attempt1)),],
          attempt2[do.call(order,as.data.frame(attempt2)),])
[1] TRUE

If you really want permutations with repetition, each function provides an argument for carrying out that function.

Since the OP is working with a wordsList with more than 3000 words and is looking for all permutations chosen 15 at a time, the aforementioned methods will fail. There are some alternatives, from iterpc as well as RcppAlgos.

With iterpc you can use the function getnext and produce successive permutations. I doubt you will be able to produce them all in a reasonable amount of time or store them in one location (i.e. assuming each cell occupies 8 bytes, 10^52 * 15 * 8/(2^80) > 10^29 YB yes... those are yobibytes... interpretation: "a lot of data").

With RcppAlgos you can utilize the rowCap argument to output a specific number of permutations up to 2^31 - 1. E.g.:

permuteGeneral(wordsList, 3, upper = 5)
        [,1]     [,2]     [,3]    
[1,] "alice"  "bravo"  "guitar"
[2,] "bravo"  "alice"  "guitar"
[3,] "guitar" "alice"  "bravo" 
[4,] "alice"  "guitar" "bravo" 
[5,] "bravo"  "guitar" "alice"

---

Related Topics