The Permutation Iterator in Python
- 时间:2020-09-13 14:33:25
- 分类:网络文摘
- 阅读:105 次
The permutation is a frequently-used algorithm that we can apply to strings, list, or arrays (vector). In Python, we can import the itertools and use the permutations method which will yield a permutation at a time – note that itertools.permutations works for both strings and list.
1 2 3 4 | >>>list(itertools.permutations([1,2,3])) [(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)] >>> list(itertools.permutations("123")) [('1', '2', '3'), ('1', '3', '2'), ('2', '1', '3'), ('2', '3', '1'), ('3', '1', '2'), ('3', '2', '1')] |
>>>list(itertools.permutations([1,2,3])) [(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)] >>> list(itertools.permutations("123")) [('1', '2', '3'), ('1', '3', '2'), ('2', '1', '3'), ('2', '3', '1'), ('3', '1', '2'), ('3', '2', '1')]
The number of total permutations is N! given the size of N elements in the string or list. For example, there are 6 permutations (3!) for a list of size 3. The fact that we may not need all permutations at once, thus we can use yield keyword that basically turns the function into returning an iterator. The iterator avoids using too much memory and is faster in practical use if you are not intending to check all permutations.
Python Permutation Iterator on List
Based on this permutation algorithm, we can recursively swap in/out the current element at position, and yield any combination result when the index reaches the end.
1 2 3 4 5 6 7 8 9 | def permutation_list(items, i = 0): if i == len(items): yield items else: for j in range(i, len(items)): items[i], items[j] = items[j], items[i] for x in permutation_list(items, i + 1): yield x items[i], items[j] = items[j], items[i] |
def permutation_list(items, i = 0): if i == len(items): yield items else: for j in range(i, len(items)): items[i], items[j] = items[j], items[i] for x in permutation_list(items, i + 1): yield x items[i], items[j] = items[j], items[i]
Calling this permutation function on list [1, 2, 3] gives the iterator that will produce the following if you convert it to list (or simply iterating over the iterator):
1 2 3 4 5 6 | [1, 2, 3] [1, 3, 2] [2, 1, 3] [2, 3, 1] [3, 2, 1] [3, 1, 2] |
[1, 2, 3] [1, 3, 2] [2, 1, 3] [2, 3, 1] [3, 2, 1] [3, 1, 2]
Note that this permutation function does not work for strings, because you simply can’t swap two characters of a string, as the strings in Python are immutable.
Python Permutation Iterator on String
The following Python permutation iterator works for Strings only. We are separating the original string into two: head and tail. Then, recursively append each character into tail until the head is empty – which means a permutation string is being yield.
1 2 3 4 5 6 7 | def permutation_string(head, tail = ''): if len(head) == 0: yield tail else: for i in range(len(head)): for s in permutation_string(head[0:i] + head[i+1:], tail+head[i]): yield s |
def permutation_string(head, tail = ''): if len(head) == 0: yield tail else: for i in range(len(head)): for s in permutation_string(head[0:i] + head[i+1:], tail+head[i]): yield s
Invoke the function on string “123” that gives the following iterator:
1 2 3 4 5 6 | 123 132 213 231 312 321 |
123 132 213 231 312 321
Permutation results look organised and are in good order. The function does not work for list as we are using a second parameter (optional) which is initialised to empty string.
Python Permutation Iterator on List and String
Let’s take a look at the following improved iterator, that works for both strings and list.
1 2 3 4 5 6 7 | def permutation(items): if len(items) <= 1: yield items else: for nextItems in permutation(items[1:]): for i in range(len(nextItems) + 1): yield nextItems[:i] + items[0:1] + nextItems[i:] |
def permutation(items): if len(items) <= 1: yield items else: for nextItems in permutation(items[1:]): for i in range(len(nextItems) + 1): yield nextItems[:i] + items[0:1] + nextItems[i:]
The [0:1] array slicing also works for strings. And the recursive permutation algorithms works by inserting current first (head) item into the other positions. And thus, the permutated results may look random and kinda dis-ordered.
1 2 3 4 5 6 | 123 213 231 132 312 321 |
123 213 231 132 312 321
–EOF (The Ultimate Computing & Technology Blog) —
推荐阅读:装修公司网销业绩不好?原因和解决方法都在这里 亚马逊正式推出企业搜索引擎Kendra 为什么Google SEO见效慢 一个三流SEOer从业记录 网站权重如何提升,掌握以下几点快速提权 SEO关键词排名该掌握的核心优化技巧 为何网站内容稳定更新还没有关键词排名? 图中阴影部分面积是多少平方厘米 梯形ABCD的面积是多少平方厘米 某校一年级同学平均身高是115厘米
- 评论列表
-
- 添加评论