如何优雅的生成“指定长度”的“指定字符集”的所有字符串？

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

已注册用户请登录

这是一个创建于 3012 天前的主题，其中的信息可能已经有所发展或是发生改变。

可能问题有点绕，题目不描述，举个例子：

如果指定长度为 3 而字符集为 abc，那就生成 aaa, aab, aac, aba ... ccc；
如果指定长度为 4 而字符集为 abcdefg，那就按顺序生成 aaaa ... gggg；

显然套 for 循环的话就没办法动态长度了，那么还有啥优雅的方法来实现吗？递归？
脑海中有那个大概思路，但写出来结果都不对…
干脆就不要脸一点… 能不能直接来段代码…

字符集

长度

指定

生成

30 条回复 • 2016-01-19 22:57:08 +08:00

windfarer

2016-01-18 23:26:45 +08:00 via Android

隐约记得 Python cookbook 里有

sensui7

2016-01-18 23:26:54 +08:00

这不就是排列组合问题吗？

yiaya

2016-01-18 23:43:56 +08:00 via Android

第一反应是在生成密码字典。。。

lxy42

2016-01-18 23:46:45 +08:00

python itertools 模块中有排列组合的函数

lxy42

2016-01-18 23:49:02 +08:00

补充，官方文档中介绍很详细，另外还有纯 python 实现的代码。

Bryan0Z

2016-01-18 23:51:57 +08:00 via Android

歪个楼，写个 26 进制转换函数，事先计算几位会数到多少，然后十进制一一数过去，转换成二十六进制，别打我
认真说: 递归

TJT

2016-01-18 23:58:46 +08:00

def fuckingfuck(maxLen, charSet, currStr):
if (len(currStr) == maxLen):
print(currStr);
return;
for i in charSet:
oldStr = currStr;
currStr += i;
fuckingfuck(maxLen, charSet, currStr);
currStr = oldStr;

fuckingfuck(3, 'abcde', '');

换成 lambda 肯定更优雅

TJT

2016-01-19 00:00:03 +08:00

https://gist.github.com/celend/476b465d5eef34c5555f

imgalaxy

2016-01-19 00:04:08 +08:00 via Android

http://ju.outofmemory.cn/entry/9594

canautumn

2016-01-19 00:04:47 +08:00

递归最优雅。不想用递归就把递归用 Stack 改写成循环。

just1

2016-01-19 00:18:04 +08:00 via Android

z2 = []

def perm( teams, k, m ):
global z2
if k > m:
z2.append( tuple(teams) )
return
else:
for i in xrange( k, m+1 ):
teams[k], teams[i] = teams[i], teams[k]
perm( teams, k+1, m )
teams[k], teams[i] = teams[i], teams[k]
return

if __name__ == '__main__':
teams = list( 'abc' )
m = len( teams )
perm( teams, 0, m-1 )
print z2
其实我是搬运工逃:)

abelyao

2016-01-19 00:30:02 +08:00

@yiaya 其实是想生成批量查域名的组合…

msg7086

2016-01-19 02:45:37 +08:00

Ruby:

input = 'abcdefg'
length = 4
input.each_char.to_a.repeated_combination(length).map(&:join)

msg7086

2016-01-19 02:48:37 +08:00

# => ["aaaa", "aaab", "aaac", "aaad", "aaae", "aaaf", "aaag", "aabb", "aabc", "aabd", "aabe", "aabf", "aabg", "aacc", "aacd", "aace", "aacf", "aacg", "aadd", "aade", "aadf", "aadg", "aaee", "aaef", "aaeg", "aaff", "aafg", "aagg", "abbb", "abbc", "abbd", "abbe", "abbf", "abbg", "abcc", "abcd", "abce", "abcf", "abcg", "abdd", "abde", "abdf", "abdg", "abee", "abef", "abeg", "abff", "abfg", "abgg", "accc", "accd", "acce", "accf", "accg", "acdd", "acde", "acdf", "acdg", "acee", "acef", "aceg", "acff", "acfg", "acgg", "addd", "adde", "addf", "addg", "adee", "adef", "adeg", "adff", "adfg", "adgg", "aeee", "aeef", "aeeg", "aeff", "aefg", "aegg", "afff", "affg", "afgg", "aggg", "bbbb", "bbbc", "bbbd", "bbbe", "bbbf", "bbbg", "bbcc", "bbcd", "bbce", "bbcf", "bbcg", "bbdd", "bbde", "bbdf", "bbdg", "bbee", "bbef", "bbeg", "bbff", "bbfg", "bbgg", "bccc", "bccd", "bcce", "bccf", "bccg", "bcdd", "bcde", "bcdf", "bcdg", "bcee", "bcef", "bceg", "bcff", "bcfg", "bcgg", "bddd", "bdde", "bddf", "bddg", "bdee", "bdef", "bdeg", "bdff", "bdfg", "bdgg", "beee", "beef", "beeg", "beff", "befg", "begg", "bfff", "bffg", "bfgg", "bggg", "cccc", "cccd", "ccce", "cccf", "cccg", "ccdd", "ccde", "ccdf", "ccdg", "ccee", "ccef", "cceg", "ccff", "ccfg", "ccgg", "cddd", "cdde", "cddf", "cddg", "cdee", "cdef", "cdeg", "cdff", "cdfg", "cdgg", "ceee", "ceef", "ceeg", "ceff", "cefg", "cegg", "cfff", "cffg", "cfgg", "cggg", "dddd", "ddde", "dddf", "dddg", "ddee", "ddef", "ddeg", "ddff", "ddfg", "ddgg", "deee", "deef", "deeg", "deff", "defg", "degg", "dfff", "dffg", "dfgg", "dggg", "eeee", "eeef", "eeeg", "eeff", "eefg", "eegg", "efff", "effg", "efgg", "eggg", "ffff", "fffg", "ffgg", "fggg", "gggg"]

msg7086

2016-01-19 02:49:33 +08:00

input.chars.repeated_combination(length).map(&:join)

这样更简单些。

Elethom

2016-01-19 07:49:21 +08:00 via iPhone

@msg7086
Ruby 竟然連這種 func 都有。長姿勢了。

virusdefender

2016-01-19 09:13:53 +08:00

burpsuite 自带

flyee

2016-01-19 09:16:42 +08:00

itertools.product('abc', repeat=3)

windfarer

2016-01-19 09:46:22 +08:00

from itertools import combinations_with_replacement
text = 'abcdef'
for c in combinations_with_replacement(text, 3):
print(''.join(c))

windfarer

2016-01-19 09:47:23 +08:00

囧，缩进没了

Arthur2e5

2016-01-19 12:25:43 +08:00

@windfarer 快用 python with braces （逃

然后日常 bash 实现：
https://gist.github.com/Arthur2e5/4c3950c8f012d1d4ae62#file-foo-bash

Arthur2e5

2016-01-19 12:39:54 +08:00

@Arthur2e5 另外里面我的确是用了 for ……所以动态长度那个是瞎讲吧？

abelyao

2016-01-19 14:56:56 +08:00

@lxy42
@imgalaxy
@just1
@msg7086
@virusdefender
@windfarer
@Arthur2e5

谢谢大家的例子，怪我一开始没说什么语言，目前我的技能树也就点亮到能看懂 C# / PHP / JS 这几个… 真的让我长见识，尤其是 ruby 那个也太狠了… 一行就搞定… 看来可以扩展一下技能树了…

@Bryan0Z 原先也想过用 26 进制来实现，然后直接从起始值 for 循环到结束值，不过貌似 26 进制也是用递归来实现的，有点多余计算了…

Bryan0Z

2016-01-19 17:09:03 +08:00 via Android

@abelyao 26 进制为什么要递归， while 不就好了

abelyao

2016-01-19 17:41:47 +08:00 via iPhone

@Bryan0Z 也对…

lululau

2016-01-19 17:47:04 +08:00

perl -le 'print for "aaa".."zzz"'

lululau

2016-01-19 17:47:41 +08:00

ruby -e '("aaa".."zzz").each { |x| puts x}'

lululau

2016-01-19 17:49:25 +08:00

ruby -e 'puts [*"aaa".."zzz"]'

windfarer

2016-01-19 21:50:45 +08:00

@lululau 逆天了

msg7086

2016-01-19 22:57:08 +08:00

@lululau 人家要求限定字符集的，用 range 做不了。