When I saw the program that lists the permutations and combinations that I made a long time ago, I couldn't immediately understand how I made it, so I tried to recreate it as a review. I will write an article so that I will not forget it.
However, the program in this article is not worth it, as it is easy to find with itertools. What's more, the official Python documentation also contains a concise and beautiful program that asks for permutations and combinations. It is just a personal study memo.
Made with Python 3.6.1.
Each shall be written as follows.
--Given data (list or tuple): data --Data length: n --Number to choose: r --Total number of permutations with duplicates: H (n, r) --Total number of permutations: P (n, r) --Total number of duplicate combinations: Π (n, r) --Total number of combinations: C (n, r)
itertools
What you are about to find can be found by using itertools.
--Duplicate permutation:
list(itertools.product(data, repeat=r))
--Permutation:
list(itertools.permutations(data, r))
--Duplicate combinations:
list(itertools.combinations_with_replacement(data, r))
--Combination:
list(itertools.combinations(data, r))
First, let's consider only the case of extracting three (r = 3) from the given data for the sake of simplicity.
Permutations with duplicates
That is. To find one pair
The process called is performed. In order to ask for all the pairs
Nest the loops like this. If you try to program immediately, it will be as follows.
result = []
for i in data:
for j in data:
for k in data:
result.append([i, j, k])
With list comprehension
result = [[i, j, k] for i in data for j in data for k in data]
However, list comprehension is not used for essential processing. Also, it's a bit verbose for later, but I'll try to find the index and then get the data content as follows:
result = []
for i in range(len(data)):
for j in range(len(data)):
for k in range(len(data)):
result.append([data[i], data[j], data[k]])
The permutation is
That is. In other words, it can be obtained by adding a process that makes it impossible to retrieve what was once retrieved to the process of permutations with duplication. Therefore, the process for finding one set is as follows.
The rest of the structure can be achieved in the same way as permutations with duplication. Alternatively, you can remove the duplicates from the permutations with duplicates. However, I will not consider this method because there are many wasted repetitions.
The program looks like this: Here, we define and use the function listExcludedIndices, which returns a list excluding the one that was once retrieved.
def listExcludedIndices(data, indices=[]):
return [x for i, x in enumerate(data) if i not in indices]
result = []
for i in range(len(data)):
for j in range(len(data) - 1):
for k in range(len(data) - 2):
jData = listExcludedIndices(data, [i])
kData = listExcludedIndices(jData, [j])
result.append([data[i], jData[j], kData[k]])
Combinations with overlap
That is.
Let's consider 2. in detail.
If the data given is [1,2,3,4], then [1,1,2] and [1,2,1] and [2,1,1] are It's the same.
In other words, unlike permutations with duplicates, if you find all the pairs that include 1s, you do not need to find the pairs that include 1s after that.
To achieve this, you can shift the start position of the nested loop.
I think it can be expressed as follows.
The program is as follows.
result = []
for i in range(len(data)):
for j in range(i, len(data)):
for k in range(j, len(data)):
result.append([data[i], data[j], data[k]])
The combination is
That is. Therefore, the process of finding one set is as follows, just like when finding the permutation.
You can shift the position of the loop in the same way as the combination with duplication. Let's make a program based on the above idea.
result = []
for i in range(len(data)):
for j in range(i, len(data) - 1):
for k in range(j, len(data) - 2):
jData = listExcludedIndices(data, [i])
kData = listExcludedIndices(jData, [j])
result.append([data[i], jData[j], kData[k]])
However, there are duplicate combinations
The purpose was to allow duplication, so if you do not allow duplication,
Can be. In other words, the program can be rewritten as follows.
result = []
for i in range(len(data)):
for j in range(i + 1, len(data)):
for k in range(j + 1, len(data)):
result.append([data[i], data[j], data[k]])
It can also be obtained by removing duplicates from duplicate combinations, such as permutations and permutations with duplicates.
In the programs up to the above, r was fixed. Since it is useless as it is, it will be made into a function. First, convert what you wrote in a fixed manner to recursion. Each has a structure in which a loop that repeats n times is nested r times. It seems that r nesting should be realized by recursive call, and n loops should be realized by one recursive call. Then, if the end condition of recursion is set to 0, it can be converted to recursion.
For permutations with duplicates, the simplest is: The value obtained in one call is taken as progress, and that value minus r is passed to the next recursive call. When r becomes 0, save the contents of progress to result and exit. The function that actually finds the element must give an initial value. Since it is difficult to use as it is, I define a wrapper function and call it.
def permutationWithRepetitionListRecursive(data, r):
if r <= 0:
return []
result = []
_permutationWithRepetitionListRecursive(data, r, [], result)
return result
def _permutationWithRepetitionListRecursive(data, r, progress, result):
if r == 0:
result.append(progress)
return
for i in range(len(data)):
_permutationWithRepetitionListRecursive(data, r - 1, progress + [data[i]], result)
Permutations do not allow re-extraction, so you can find them by adding that process. In the permutation with duplication, data was passed to the next call as it is, but here we will pass the rest excluding the one retrieved once.
def permutationListRecursive(data, r):
if r <= 0 or r > len(data):
return []
result = []
_permutationListRecursive(data, r, [], result)
return result
def _permutationListRecursive(data, r, progress, result):
if r == 0:
result.append(progress)
return
for i in range(len(data)):
_permutationListRecursive(listExcludedIndices(data, [i]), r - 1, progress + [data[i]], result)
For duplicate combinations, add an argument that represents the start position, give that argument the current fetch position, and make the next recursive call. Other than that, there is no difference from permutations with duplicates.
def combinationWithRepetitionListRecursive(data, r):
if r <= 0:
return []
result = []
_combinationWithRepetitionListRecursive(data, r, 0, [], result)
return result
def _combinationWithRepetitionListRecursive(data, r, start, progress, result):
if r == 0:
result.append(progress)
return
for i in range(start, len(data)):
_combinationWithRepetitionListRecursive(data, r - 1, i, progress + [data[i]], result)
The combination ensures that the next recursive call is made one step ahead of the current fetch position.
def combinationListRecursive(data, r):
if r == 0 or r > len(data):
return []
result = []
_combinationListRecursive(data, r, 0, [], result)
return result
def _combinationListRecursive(data, r, start, progress, result):
if r == 0:
result.append(progress)
return
for i in range(start, len(data)):
#Another solution_combinationListRecursive(listExcludedIndices(data, [i]), r - 1, i, progress + [data[i]], result)
_combinationListRecursive(data, r - 1, i + 1, progress + [data[i]], result)
Recursion is dangerous because it can cause stack overflow, so consider a function that uses a loop. Basically, it takes r loops to find one element, and you only have to repeat it as many times as you need. The total number of each is officially calculated immediately, so use that. In addition, in the following, we are considering a solution method based on the position (index) to take out all.
If n = 4 and r = 3, the permutations with duplicates to be found are as follows.
00: 0 0 0 -> data[0] data[0] data[0]
01: 0 0 1 -> data[0] data[0] data[1]
02: 0 0 2 -> data[0] data[0] data[2]
03: 0 0 3 -> data[0] data[0] data[3]
04: 0 1 0 -> data[0] data[1] data[0]
05: 0 1 1 -> data[0] data[1] data[1]
06: 0 1 2 -> data[0] data[1] data[2]
07: 0 1 3 -> data[0] data[1] data[3]
08: 0 2 0 -> data[0] data[1] data[0]
09: 0 2 1 -> data[0] data[1] data[1]
10: 0 2 2 -> data[0] data[1] data[2]
11: 0 2 3 -> data[0] data[1] data[3]
...
Duplicate permutations are the same as finding r-digit n-ary numbers.
When the number of digits is represented by d, each digit counts up every n ^ d in the same way as an n-ary number.
If you represent some element by i now, you can find the index of that digit by dividing i by n ^ d.
This will exceed the size of the data, so you need to divide it by n as the remainder.
The program looks like this:
import math
def permutationWithRepetition(n, r):
return int(pow(n, r))
def permutationWithRepetitionList(data, r):
length = len(data)
total = permutationWithRepetition(length, r)
result = []
for i in range(total):
element = []
for digit in reversed(range(r)):
element.append(data[int(i / pow(length, digit)) % length])
result.append(element)
return result
If n = 4 and r = 3, the permutation to be obtained is as follows.
00: 0 1 2 -> data[0] data[1] data[2]
01: 0 1 3 -> data[0] data[1] data[3]
02: 0 2 1 -> data[0] data[2] data[1]
03: 0 2 3 -> data[0] data[2] data[3]
04: 0 3 1 -> data[0] data[3] data[1]
05: 0 3 2 -> data[0] data[3] data[2]
06: 1 0 2 -> data[1] data[0] data[2]
07: 1 0 3 -> data[1] data[0] data[3]
08: 1 2 0 -> data[1] data[2] data[0]
09: 1 2 3 -> data[1] data[2] data[3]
10: 1 3 0 -> data[1] data[3] data[0]
11: 1 3 2 -> data[1] data[3] data[2]
12: 2 0 1 -> data[2] data[0] data[1]
13: 2 0 3 -> data[2] data[0] data[3]
14: 2 1 0 -> data[2] data[1] data[0]
15: 2 1 3 -> data[2] data[1] data[3]
16: 2 3 0 -> data[2] data[3] data[0]
17: 2 3 1 -> data[2] data[3] data[1]
18: 3 0 1 -> data[3] data[0] data[1]
19: 3 0 2 -> data[3] data[0] data[2]
20: 3 1 0 -> data[3] data[1] data[0]
21: 3 1 2 -> data[3] data[1] data[2]
22: 3 2 0 -> data[3] data[2] data[0]
23: 3 2 1 -> data[3] data[2] data[2]
This is also likely to be obtained from the element number i and digit d.
First, consider the third digit. The same number appears from 1 to 4. In other words, if you divide P (n, r) by n, you can find the position to count up.
Consider the second digit. Here, numbers other than those appearing in the third digit will appear. The total number is n-1. This will appear evenly when the third digit is the same number. In other words, it counts up with P (n, r) / (n \ * n-1).
If you think about the first digit in the same way, you can see that it counts up with P (n, r) / (n \ * n-1 \ * n-2).
Let's make a program from the above idea.
import math
import functools
import operator
def permutation(n, r):
if(n < r):
return 0
return int(math.factorial(n) / math.factorial(n - r))
def permutationList(data, r):
length = len(data)
total = permutation(length, r)
result = []
for i in range(total):
element = []
copyData = data[:]
for digit in range(r):
l = len(copyData)
countUp = total / functools.reduce(operator.mul, range(l, length + 1))
index = int(i / countUp) % l
element.append(copyData.pop(index))
result.append(element)
return result
If n = 4 and r = 3, the combinations with duplication to be obtained are as follows.
00: 0 0 0 -> data[0] data[0] data[0]
01: 0 0 1 -> data[0] data[0] data[1]
02: 0 0 2 -> data[0] data[0] data[2]
03: 0 0 3 -> data[0] data[0] data[3]
04: 0 1 1 -> data[0] data[1] data[1]
05: 0 1 2 -> data[0] data[1] data[2]
06: 0 1 3 -> data[0] data[1] data[3]
07: 0 2 2 -> data[0] data[2] data[2]
08: 0 2 3 -> data[0] data[2] data[3]
09: 0 3 3 -> data[0] data[3] data[3]
10: 1 1 1 -> data[1] data[1] data[1]
11: 1 1 2 -> data[1] data[1] data[2]
12: 1 1 3 -> data[1] data[1] data[3]
13: 1 2 2 -> data[1] data[2] data[2]
14: 1 2 3 -> data[1] data[2] data[3]
15: 1 3 3 -> data[1] data[3] data[3]
16: 2 2 2 -> data[2] data[2] data[2]
17: 2 2 3 -> data[2] data[2] data[3]
18: 2 3 3 -> data[2] data[3] data[3]
19: 3 3 3 -> data[3] data[3] data[3]
This seems to be difficult to find from the element number, so try to find the next element from the previous element. Focusing on the 1st digit, the previous value is +1 except where the 2nd or 3rd digit has been changed. Therefore, it seems that it can be controlled by detecting the count-up of the 2nd and 3rd digits. If you extract the place where the second digit counts up,
0 0 3 -> 0 1 1
0 1 3 -> 0 2 2
0 2 3 -> 0 3 3
What they have in common is
--The first digit of the previous element is 3 --The second digit is incremented by +1 --The first and second digits are the same
is. In the same way, if you extract the place where the third digit counts up,
0 3 3 -> 1 1 1
1 3 3 -> 2 2 2
2 3 3 -> 3 3 3
What they have in common is
--The second digit of the previous element is 3 --Third digit is incremented by +1 --Third digit, second digit and first digit are the same
is.
If you put this into a function
--N-1 comes to the i digit of the previous element --i + 1 add +1 to the first digit --Make i + 1 digits and later the same as i + 1 digits
It will be good. It's a messy program, but it looks like this: Here, we define and use getListElements, a function that calculates the value from a set of indexes.
def getListElements(lis, indices):
"""Returns the set of elements indicated by indexes from list"""
return [lis[i] for i in indices]
import math
def combinationWithRepetition(n, r):
return int(math.factorial(r + n - 1) / (math.factorial(r) * math.factorial(n - 1)))
def updateCombinationIndex(lastIndex, start, repetition=False):
result = lastIndex[:start]
x = lastIndex[start] + 1
for i in range(start, len(lastIndex)):
result.append(x)
if(repetition == False):
x += 1
return result
def getComginationWithRepetitionIndex(length, r, lastIndex):
result = []
for i in range(r):
if(len(lastIndex) == 0):
result.append(0)
elif(lastIndex[i] >= length - 1):
result = updateCombinationIndex(lastIndex, i - 1, True)
break
elif(i == r - 1):
result = updateCombinationIndex(lastIndex, i, True)
return result
def combinationWithRepetitionList(data, r):
length = len(data)
total = combinationWithRepetition(length, r)
result = []
lastIndex = []
for i in range(total):
lastIndex = getComginationWithRepetitionIndex(length, r, lastIndex)
result.append(getListElements(data, lastIndex))
return result
If n = 4 and r = 3, the combination to be obtained is as follows.
00: 0 1 2 -> data[0] data[1] data[2]
01: 0 1 3 -> data[0] data[1] data[3]
02: 0 2 3 -> data[0] data[2] data[3]
03: 1 2 3 -> data[1] data[2] data[3]
I will try to find it in the same way as the combination with duplication. It is difficult to understand because there are few concrete examples, but the place where the second digit counts up is
--The first digit of the previous element is 3 --The second digit is incremented by +1 ――The first digit becomes the second digit +1
The place where the third digit counts up is
--The second digit of the previous element is 2 --Third digit is incremented by +1 ――The second digit becomes the third digit +1 ――The first digit becomes the second digit +1
It is like that.
--N-i comes to the i digit of the previous element --i + 1 add +1 to the first digit --i + 1-Set the nth digit to the element of i + 1 + n
If you change the conditions for counting up and the changes, you can make it in the same way as a combination with duplication. The program looks like this:
import math
def combination(n, r):
if(n < r):
return 0
return int(math.factorial(n) / (math.factorial(r) * math.factorial(n - r)))
def getComginationIndex(length, r, lastIndex):
result = []
for i in range(r):
if(len(lastIndex) == 0):
result.append(i)
elif(lastIndex[i] >= length - r + i):
result = updateCombinationIndex(lastIndex, i - 1, False)
break
elif(i == r - 1):
result = updateCombinationIndex(lastIndex, i, False)
return result
def combinationList(data, r):
length = len(data)
total = combination(length, r)
result = []
lastIndex = []
for i in range(total):
lastIndex = getComginationIndex(length, r, lastIndex)
result.append(getListElements(data, lastIndex))
return result
Since I made it with Python, I will try it as a generator. I know that the recursive version of the generator works if I write it like this, but I'm not sure why I should do it. Also, it is not known that if the recursive generator is stopped at a deep stack, the memory will be overloaded.
If you create it with only yield, it will be as follows.
I'm yield to return a value when r is 0, and since the recursive function itself returns a generalta, I'm turning it with a for statement.
I tried to use the data passed to the recursive function as a generator, but I couldn't realize it because of the difficulty so far.
def permutationWithRepetitionGeneratorRecursive(data, r):
if r <= 0:
return []
return _permutationWithRepetitionGeneratorRecursive(data, r, [])
def _permutationWithRepetitionGeneratorRecursive(data, r, progress):
if r == 0:
yield progress
return
for i in range(len(data)):
for j in _permutationWithRepetitionGeneratorRecursive(data, r - 1, progress + [data[i]]):
yield j
Using yield from, we get:
Two yields came out and it wasn't moody, so it feels nice and refreshing.
def _permutationWithRepetitionGeneratorRecursive(data, r, progress):
if r == 0:
yield progress
return
for i in range(len(data)):
yield from _permutationWithRepetitionGeneratorRecursive(data, r - 1, progress + [data[i]])
def permutationGeneratorRecursive(data, r):
if r <= 0 or r > len(data):
return []
return _permutationGeneratorRecursive(data, r, [])
def _permutationGeneratorRecursive(data, r, progress):
if r == 0:
yield progress
return
for i in range(len(data)):
yield from _permutationGeneratorRecursive(listExcludedIndices(data, [i]), r - 1, progress + [data[i]])
def combinationWithRepetitionGeneratorRecursive(data, r):
if r <= 0:
return []
return _combinationWithRepetitionGeneratorRecursive(data, r, 0, [])
def _combinationWithRepetitionGeneratorRecursive(data, r, start, progress):
if r == 0:
yield progress
return
for i in range(start, len(data)):
yield from _combinationWithRepetitionGeneratorRecursive(data, r - 1, i, progress + [data[i]])
def combinationGeneratorRecursive(data, r):
if r == 0 or r > len(data):
return []
return _combinationGeneratorRecursive(data, r, 0, [])
def _combinationGeneratorRecursive(data, r, start, progress):
if r == 0:
yield progress
return
for i in range(start, len(data)):
yield from _combinationGeneratorRecursive(data, r - 1, i + 1, progress + [data[i]])
def permutationWithRepetitionGenerator(data, r):
length = len(data)
total = permutationWithRepetition(length, r)
for i in range(total):
element = []
for digit in reversed(range(r)):
element.append(data[int(i / pow(length, digit)) % length])
yield element
def permutationGenerator(data, r):
length = len(data)
total = permutation(length, r)
for i in range(total):
element = []
copyData = data[:]
for digit in range(r):
l = len(copyData)
countUp = total / functools.reduce(operator.mul, range(l, length + 1))
index = int(i / countUp) % l
element.append(copyData.pop(index))
yield element
def combinationWithRepetitionGenerator(data, r):
length = len(data)
total = combinationWithRepetition(length, r)
lastIndex = []
for i in range(total):
lastIndex = getComginationWithRepetitionIndex(length, r, lastIndex)
yield getListElements(data, lastIndex)
def combinationGenerator(data, r):
length = len(data)
total = combination(length, r)
lastIndex = []
for i in range(total):
lastIndex = getComginationIndex(length, r, lastIndex)
yield getListElements(data, lastIndex)
It's difficult in words. Rather than thinking about the theory / solution and then making it into a program, I felt like I was thinking of a solution / theory from the program, so the text was not very good. In addition, there are places where explanations are skipped. That's where I didn't understand enough or I was wondering what to do with the expression.
def combinations(iterable, r):
# combinations('ABCD', 2) --> AB AC AD BC BD CD
# combinations(range(4), 3) --> 012 013 023 123
pool = tuple(iterable)
n = len(pool)
if r > n:
return
indices = list(range(r))
yield tuple(pool[i] for i in indices)
while True:
for i in reversed(range(r)):
if indices[i] != i + n - r:
break
else:
return
indices[i] += 1
for j in range(i+1, r):
indices[j] = indices[j-1] + 1
yield tuple(pool[i] for i in indices)
def combinations(iterable, r):
pool = tuple(iterable)
n = len(pool)
for indices in permutations(range(n), r):
if sorted(indices) == list(indices):
yield tuple(pool[i] for i in indices)
def combinations_with_replacement(iterable, r):
# combinations_with_replacement('ABC', 2) --> AA AB AC BB BC CC
pool = tuple(iterable)
n = len(pool)
if not n and r:
return
indices = [0] * r
yield tuple(pool[i] for i in indices)
while True:
for i in reversed(range(r)):
if indices[i] != n - 1:
break
else:
return
indices[i:] = [indices[i] + 1] * (r - i)
yield tuple(pool[i] for i in indices)
def combinations_with_replacement(iterable, r):
pool = tuple(iterable)
n = len(pool)
for indices in product(range(n), repeat=r):
if sorted(indices) == list(indices):
yield tuple(pool[i] for i in indices)
def permutations(iterable, r=None):
# permutations('ABCD', 2) --> AB AC AD BA BC BD CA CB CD DA DB DC
# permutations(range(3)) --> 012 021 102 120 201 210
pool = tuple(iterable)
n = len(pool)
r = n if r is None else r
if r > n:
return
indices = list(range(n))
cycles = list(range(n, n-r, -1))
yield tuple(pool[i] for i in indices[:r])
while n:
for i in reversed(range(r)):
cycles[i] -= 1
if cycles[i] == 0:
indices[i:] = indices[i+1:] + indices[i:i+1]
cycles[i] = n - i
else:
j = cycles[i]
indices[i], indices[-j] = indices[-j], indices[i]
yield tuple(pool[i] for i in indices[:r])
break
else:
return
def permutations(iterable, r=None):
pool = tuple(iterable)
n = len(pool)
r = n if r is None else r
for indices in product(range(n), repeat=r):
if len(set(indices)) == r:
yield tuple(pool[i] for i in indices)
def product(*args, repeat=1):
# product('ABCD', 'xy') --> Ax Ay Bx By Cx Cy Dx Dy
# product(range(2), repeat=3) --> 000 001 010 011 100 101 110 111
pools = [tuple(pool) for pool in args] * repeat
result = [[]]
for pool in pools:
result = [x+[y] for x in result for y in pool]
for prod in result:
yield tuple(prod)
Recommended Posts