首页   注册   登录
V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX 提问指南
abelyao
V2EX  ›  问与答

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

  •  1
     
  •   abelyao · 2016-01-18 23:18:21 +08:00 · 3356 次点击
    这是一个创建于 1468 天前的主题,其中的信息可能已经有所发展或是发生改变。

    可能问题有点绕,题目不描述,举个例子:

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

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

    30 回复  |  直到 2016-01-19 22:57:08 +08:00
    windfarer
        1
    windfarer   2016-01-18 23:26:45 +08:00 via Android
    隐约记得 Python cookbook 里有
    sensui7
        2
    sensui7   2016-01-18 23:26:54 +08:00
    这不就是排列组合问题吗?
    yiaya
        3
    yiaya   2016-01-18 23:43:56 +08:00 via Android
    第一反应是在生成密码字典。。。
    lxy42
        4
    lxy42   2016-01-18 23:46:45 +08:00
    python itertools 模块中有排列组合的函数
    lxy42
        5
    lxy42   2016-01-18 23:49:02 +08:00
    补充,官方文档中介绍很详细,另外还有纯 python 实现的代码。
    Bryan0Z
        6
    Bryan0Z   2016-01-18 23:51:57 +08:00 via Android
    歪个楼,写个 26 进制转换函数,事先计算几位会数到多少,然后十进制一一数过去,转换成二十六进制,别打我
    认真说: 递归
    TJT
        7
    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
        8
    TJT   2016-01-19 00:00:03 +08:00
    imgalaxy
        9
    imgalaxy   2016-01-19 00:04:08 +08:00 via Android
    canautumn
        10
    canautumn   2016-01-19 00:04:47 +08:00
    递归最优雅。不想用递归就把递归用 Stack 改写成循环。
    just1
        11
    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
        12
    abelyao   2016-01-19 00:30:02 +08:00
    @yiaya 其实是想生成批量查域名的组合…
    msg7086
        13
    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
        14
    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
        15
    msg7086   2016-01-19 02:49:33 +08:00
    input.chars.repeated_combination(length).map(&:join)

    这样更简单些。
    Elethom
        16
    Elethom   2016-01-19 07:49:21 +08:00 via iPhone
    @msg7086
    Ruby 竟然連這種 func 都有。長姿勢了。
    virusdefender
        17
    virusdefender   2016-01-19 09:13:53 +08:00
    burpsuite 自带
    flyee
        18
    flyee   2016-01-19 09:16:42 +08:00
    itertools.product('abc', repeat=3)
    windfarer
        19
    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
        20
    windfarer   2016-01-19 09:47:23 +08:00
    囧,缩进没了
    Arthur2e5
        21
    Arthur2e5   2016-01-19 12:25:43 +08:00
    @windfarer 快用 python with braces (逃

    然后日常 bash 实现:
    #file-foo-bash
    Arthur2e5
        22
    Arthur2e5   2016-01-19 12:39:54 +08:00
    @Arthur2e5 另外里面我的确是用了 for ……所以动态长度那个是瞎讲吧?
    abelyao
        23
    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
        24
    Bryan0Z   2016-01-19 17:09:03 +08:00 via Android
    @abelyao 26 进制为什么要递归, while 不就好了
    abelyao
        25
    abelyao   2016-01-19 17:41:47 +08:00 via iPhone
    @Bryan0Z 也对…
    lululau
        26
    lululau   2016-01-19 17:47:04 +08:00
    perl -le 'print for "aaa".."zzz"'
    lululau
        27
    lululau   2016-01-19 17:47:41 +08:00
    ruby -e '("aaa".."zzz").each { |x| puts x}'
    lululau
        28
    lululau   2016-01-19 17:49:25 +08:00   ♥ 1
    ruby -e 'puts [*"aaa".."zzz"]'
    windfarer
        29
    windfarer   2016-01-19 21:50:45 +08:00
    @lululau 逆天了
    msg7086
        30
    msg7086   2016-01-19 22:57:08 +08:00
    @lululau 人家要求限定字符集的,用 range 做不了。
    关于   ·   FAQ   ·   API   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   2108 人在线   最高记录 5168   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.3 · 41ms · UTC 12:30 · PVG 20:30 · LAX 04:30 · JFK 07:30
    ♥ Do have faith in what you're doing.