搜索
首页后端开发php教程给定一个字符串,返回所有的可能组合

例:abc
返回a,b,c,ab,ac,bc,ca,cb,abc,acb,bac,bca,cab,cba

回复内容:

例:abc
返回a,b,c,ab,ac,bc,ca,cb,abc,acb,bac,bca,cab,cba

我覺得這個問題相當有趣,做為一個 Python 狂熱者,我不能同意 @garry_qian 的答案更多了,既然 Python 都提供了那麼好用的標準庫,不使用一下實在是太可惜了,在此立場下,一個 簡潔,簡短 (好啦並沒有...),但邏輯上基本相同的做法如下:

<code>>>> s = 'abc'
>>> results = sorted([''.join(c) for l in range(len(s)) for c in permutations(s, l+1)])

['a', 'b', 'c', 'ab', 'ac', 'ba', 'bc', 'ca', 'cb', 'abc', 'acb', 'bac', 'bca', 'cab', 'cba']</code>

這個寫法沒什麼特別的,不過是使用兩個 forlist comprehension 罷了。
同時,它回傳的是一個 string 的 list,與原題目比較接近。


但是這激發了我的一些好奇心,想自己來寫寫看,同時以沒有這些排列組合工具的他種語言來說,也許比較容易利用相同的邏輯來完成。

首先我完成的是關於組合的 function,他代入一個字串並且回傳所有長度的所有字元組合,但不排列:

<code>def get_combinations(string):
    combs = []
    for i in range(1, 2**len(string)):
        pat = "{0:b}".format(i).zfill(len(string))
        combs.append(''.join(c for c, b in zip(string, pat) if int(b)))
    return combs</code>

測試:

<code>>>> print get_combinations('abc')
['c', 'b', 'bc', 'a', 'ac', 'ab', 'abc']</code>

一如預期,我們拿到:

  1. 長度為 1 的 'c', 'b', 'a'

  2. 長度為 2 的 'bc', 'ac', 'ab'

  3. 長度為 3 的 'abc'

果然是各種長度下的所有組合都到手了。

這個寫法肯定不是最好的,但我覺得想法滿有趣的。想法就是,要考慮 'abc' 的所有組合,那不就是分別考慮 a 要不要取,b 要不要取 和 c 要不要取,於是總共 2*2*2 = 8 (2**len(string)) 種組合,那不就正好對應到:

<code>000 -> 都不取
001 -> 只取 c
010 -> 只取 b
011 -> 取 b c
100 -> 只取 a
101 -> 取 a c
110 -> 取 a b
111 -> 都取</code>

所以在 get_combinations 中,用了一點技巧去生出從 1 到 7 的二進位碼,再根據 0 與 1 決定每一種組合該取用那些字元。


這還沒完成任務,我們距離標準答案,還必須取得:

每一種 組合 的所有 排列 情形

這產生了 get_permutations 這個 function:

<code>def get_permutations(clst):
    if len(clst)==1:
        return [clst[0]]
    results = []
    for idx, c in enumerate(clst):
        results += [c+substr for substr in get_permutations(clst[:idx] + clst[idx+1:])]
    return results</code>

測試:

<code>>>> print get_permutations('abc')
['abc', 'acb', 'bac', 'bca', 'cab', 'cba']</code>

邏輯很簡單,用 recursive 的方式去找出 固定長度字元組合 所有的排列。


有了以上兩種 function,我們就可以求出答案囉:

<code>>>> [perm for comb in get_combinations('abc') for perm in get_permutations(list(comb))]
['c', 'b', 'bc', 'cb', 'a', 'ac', 'ca', 'ab', 'ba', 'abc', 'acb', 'bac', 'bca', 'cab', 'cba']</code>

結論:

  1. 別重複發明輪胎,這不但累死你,還很顯笨

  2. 人生苦短,我用 Python

<code>import itertools

chrs = 'abc'

for i in range(len(chrs)):
    for combination in itertools.permutations(chrs, i + 1):
        print combination</code>

既然同时打了 phppython 标签,那就用两种方式都写下吧,逻辑用的一样的。

php代码

function addChar($strs, $chars) {
    $result = [];
    foreach ($strs as $str) {
        foreach ($chars as $char) {
            $result[] = $str . $char;
        }
    }
    return $result;
}

$chars  = ['a', 'b', 'c'];

$group = [];
$count = count($chars);
for ($i = 1; $i <= $count; $i++) { 
    if ($i == 1) {
        $group[$i] = addChar([''], $chars);
    } else {
        $group[$i] = addChar($group[$i - 1], $chars);
    }
}

// 合并数组
$result = call_user_func_array('array_merge', $group);

var_dump($group);

python代码

# encoding:utf-8

def addChar(strs, chars):
    result = []
    for str in strs:
        for char in chars:
            result.append(str + char)
    return result



chars = ['a', 'b', 'c']

group = {}
count = len(chars)

for i in xrange(1, count + 1):
    if i == 1:
        group[i] = addChar([''], chars)
    else:
        group[i] = addChar(group[i - 1], chars)

# 合并数组
result = []
for i in group:
    result += group[i]

print result

<code>result = [] 

def function(arg, string):
    global result

    if len(arg) >= len(string):
        return None 

    for alphabet in string:
        if alphabet in arg:
            continue
        function(arg+alphabet, string)
        result.append(arg+alphabet)

string = 'abc'

for alphabet in string:
    result.append(alphabet)
    function(alphabet, string)

print list(set(result))</code>

python2.7,和@garry_qian 相同,写完才发现有了,其他楼的python方案我都懒得看了

# coding: utf-8
import itertools as t

li = ['a', 'b', 'c']
tmp = []
for n in range(1, len(li) + 1):
    x = t.permutations(li, n)
    for i in x:
        tmp.append(''.join(i))
print tmp

P(2,3)
P(3,3)
12种可能性

假设字符串的长度为2, 那所有的组合就是: 2! + 2! / 1! = 4
假设字符串的长度为3, 那所有的组合就是: 3! + 3! / 1! + 3! / 2! = 15
假设字符串的长度为4, 那所有的组合就是: 4! + 4! / 1! + 4! / 2! + 4! / 3! = 64
这个公式可以进行推广
n! + n! / 1! + n! / 2! + ... + n! / (n-1)!

代码就不贴了

声明
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn
php怎么把负数转为正整数php怎么把负数转为正整数Apr 19, 2022 pm 08:59 PM

php把负数转为正整数的方法:1、使用abs()函数将负数转为正数,使用intval()函数对正数取整,转为正整数,语法“intval(abs($number))”;2、利用“~”位运算符将负数取反加一,语法“~$number + 1”。

php怎么实现几秒后执行一个函数php怎么实现几秒后执行一个函数Apr 24, 2022 pm 01:12 PM

实现方法:1、使用“sleep(延迟秒数)”语句,可延迟执行函数若干秒;2、使用“time_nanosleep(延迟秒数,延迟纳秒数)”语句,可延迟执行函数若干秒和纳秒;3、使用“time_sleep_until(time()+7)”语句。

php怎么除以100保留两位小数php怎么除以100保留两位小数Apr 22, 2022 pm 06:23 PM

php除以100保留两位小数的方法:1、利用“/”运算符进行除法运算,语法“数值 / 100”;2、使用“number_format(除法结果, 2)”或“sprintf("%.2f",除法结果)”语句进行四舍五入的处理值,并保留两位小数。

php怎么根据年月日判断是一年的第几天php怎么根据年月日判断是一年的第几天Apr 22, 2022 pm 05:02 PM

判断方法:1、使用“strtotime("年-月-日")”语句将给定的年月日转换为时间戳格式;2、用“date("z",时间戳)+1”语句计算指定时间戳是一年的第几天。date()返回的天数是从0开始计算的,因此真实天数需要在此基础上加1。

php怎么替换nbsp空格符php怎么替换nbsp空格符Apr 24, 2022 pm 02:55 PM

方法:1、用“str_replace("&nbsp;","其他字符",$str)”语句,可将nbsp符替换为其他字符;2、用“preg_replace("/(\s|\&nbsp\;||\xc2\xa0)/","其他字符",$str)”语句。

php怎么判断有没有小数点php怎么判断有没有小数点Apr 20, 2022 pm 08:12 PM

php判断有没有小数点的方法:1、使用“strpos(数字字符串,'.')”语法,如果返回小数点在字符串中第一次出现的位置,则有小数点;2、使用“strrpos(数字字符串,'.')”语句,如果返回小数点在字符串中最后一次出现的位置,则有。

php字符串有没有下标php字符串有没有下标Apr 24, 2022 am 11:49 AM

php字符串有下标。在PHP中,下标不仅可以应用于数组和对象,还可应用于字符串,利用字符串的下标和中括号“[]”可以访问指定索引位置的字符,并对该字符进行读写,语法“字符串名[下标值]”;字符串的下标值(索引值)只能是整数类型,起始值为0。

php怎么读取字符串后几个字符php怎么读取字符串后几个字符Apr 22, 2022 pm 08:31 PM

在php中,可以使用substr()函数来读取字符串后几个字符,只需要将该函数的第二个参数设置为负值,第三个参数省略即可;语法为“substr(字符串,-n)”,表示读取从字符串结尾处向前数第n个字符开始,直到字符串结尾的全部字符。

See all articles

热AI工具

Undresser.AI Undress

Undresser.AI Undress

人工智能驱动的应用程序,用于创建逼真的裸体照片

AI Clothes Remover

AI Clothes Remover

用于从照片中去除衣服的在线人工智能工具。

Undress AI Tool

Undress AI Tool

免费脱衣服图片

Clothoff.io

Clothoff.io

AI脱衣机

AI Hentai Generator

AI Hentai Generator

免费生成ai无尽的。

热门文章

R.E.P.O.能量晶体解释及其做什么(黄色晶体)
2 周前By尊渡假赌尊渡假赌尊渡假赌
仓库:如何复兴队友
4 周前By尊渡假赌尊渡假赌尊渡假赌
Hello Kitty Island冒险:如何获得巨型种子
4 周前By尊渡假赌尊渡假赌尊渡假赌

热工具

SublimeText3 Mac版

SublimeText3 Mac版

神级代码编辑软件(SublimeText3)

mPDF

mPDF

mPDF是一个PHP库,可以从UTF-8编码的HTML生成PDF文件。原作者Ian Back编写mPDF以从他的网站上“即时”输出PDF文件,并处理不同的语言。与原始脚本如HTML2FPDF相比,它的速度较慢,并且在使用Unicode字体时生成的文件较大,但支持CSS样式等,并进行了大量增强。支持几乎所有语言,包括RTL(阿拉伯语和希伯来语)和CJK(中日韩)。支持嵌套的块级元素(如P、DIV),

SublimeText3汉化版

SublimeText3汉化版

中文版,非常好用

EditPlus 中文破解版

EditPlus 中文破解版

体积小,语法高亮,不支持代码提示功能

VSCode Windows 64位 下载

VSCode Windows 64位 下载

微软推出的免费、功能强大的一款IDE编辑器