今天面试的一道算法题，求教

itertools 的逻辑，可以参考下官方给的代码。

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)

gclove

2018-03-21 23:26:53 +08:00

1,3,5 为什么不行，@acros 机智

lance6716276

2018-03-21 23:43:21 +08:00 via Android

C5，3 是 10 啊…要有十个啊…

whoami9894

2018-03-21 23:57:34 +08:00 via Android

@gclove 对呀 1.3.4 为啥也不行

junkiedon

2018-03-22 00:02:37 +08:00

DFS

kunluanbudang

2018-03-22 00:15:01 +08:00

把自己在 leetcode 上的垃圾代码粘贴一次
:)

```
class Solution:
def __init__(self, ):
self._res = []

def combine(self, n,k):
if (n <= 0) or (k <= 0) or (k > n):
return []
else:
c = []
self.generate_combinations(n, k, 1, c)
return self._res

def generate_combinations(self, n, k, start, c):
if len(c) == k:
self._res.append(copy.deepcopy(c))
return
else:
i = start
maxI = n - (k-len(c) )+ 1
while i <= maxI:
print(c)
c.append(i)
self.generate_combinations(n, k, i+1, c)
c.pop()

i += 1
return
```

takeoffyoung

2018-03-22 00:23:09 +08:00

https://paste.ubuntu.com/p/bpWH2vthHc/

kkzxak47

2018-03-22 00:24:23 +08:00 via Android

一帮不看题的，做完说题出错了

neoblackcap

2018-03-22 00:44:30 +08:00

@kkzxak47 从题主描述问题就是一个排列问题 Combination(5,3)=10，但是跟题目期望不同，要不题目少了条件，否则就是题主记错例子。

ujued

2018-03-22 00:44:57 +08:00 via iPhone

这 m 个数，前 m-1 个是连续的，整体递增的。这样还不好实现？

kkzxak47

2018-03-22 01:03:20 +08:00 via Android

@neoblackcap 你还在这排列组合……

neoblackcap

2018-03-22 01:24:10 +08:00

@kkzxak47 这题不考排列组合考什么呢？我看了 5 分钟，没看出其他意思，的确没看出排列以外的意思。

markx

2018-03-22 01:26:31 +08:00

@kkzxak47 题目确实没说清楚。“获取长度为 M 的集合”，如果是要数组元素的集合的话，那这个确实是求排列，跟例子不符啊。

要不然你说一说你对题目的理解？

markx

2018-03-22 01:27:34 +08:00

@kkzxak47 啊…… 不是排列，是组合。

VincentBu

2018-03-22 02:16:30 +08:00

典型的 backtracking 题目

pyufftj

2018-03-22 08:09:06 +08:00

@264768502 哈哈，当时面试的时候我也有类似的经历。当时让我统计某种特征最多的几个数，我当时使用 Counter 库，两行代码搞定，面试官都蒙了。不过肯定是让你实现底层代码，这样做面试官肯定不满意吧

Hopetree

2018-03-22 08:54:05 +08:00

为什么不是 [{1, 2, 3}, {1, 2, 4}, {1, 2, 5}, {1, 3, 4}, {1, 3, 5}, {1, 4, 5}, {2, 3, 4}, {2, 3, 5}, {2, 4, 5}, {3, 4, 5}]

rebeccaMyKid

2018-03-22 08:59:28 +08:00

@Hopetree 对啊，怎么才这么几个呀。我都准备贴代码了

rebeccaMyKid

2018-03-22 09:07:53 +08:00

组合
https://gist.github.com/ajfg93/aa78065e6b50e866c52743ab8aeb6e1d
排列
https://gist.github.com/ajfg93/8accdcb540d0e1006f4b789a894f45d7

:D

faceRollingKB

2018-03-22 09:26:37 +08:00

简单想下，数组 N 长度 M 的集合 Arr(N)*L(M)=n1*Arr(N-n1)*L(M-1)+Arr(N-n1)*L(M)
一个递归甩上去呗

crane2018

2018-03-22 09:55:33 +08:00

就是说输出结果数组的 index 顺序还要满足源数组的 index 大小顺序，而且输出结果数组的前两个数在源数组中相邻，and that's all

cs5791393

2018-03-22 09:55:50 +08:00

用递归写个循环不就能解决了吗

di94sh

2018-03-22 10:17:00 +08:00

``` python
def combination(numlist, m, low=0):
if m==0:
yield []
else:
for i in range(low, len(numlist)):
for rest in combination(numlist, m - 1, i + 1):
yield [numlist[i]] + rest

def combinations(numlist, m):
return list(combination(numlist, m))
numlist = [1, 2, 3, 4, 5]
print(combinations(numlist, 3))
```

di94sh

2018-03-22 10:26:14 +08:00

https://gist.github.com/xuaoao/d0b1c927996e3e2806674610d43ad83f

UnknownR

2018-03-22 10:40:26 +08:00

@rebeccaMyKid 一点显示 gist 代码，chrome 就卡成狗。。。滚屏特别卡

mathzhaoliang

2018-03-22 10:52:06 +08:00

@di94sh 递归的话效率不高，而且 python 里面有层数限制。

kkzxak47

2018-03-22 12:28:58 +08:00 via Android

@neoblackcap

题目的输出样例是摆看的吗？
{1,2,3}{1,2,4},{1,2,5},
{2,3,4},{2,3,5}
{3,4,5}
为什么一旦题设不符合你的思维定势，就无所适从，真的不能稍微多想一点点吗？

yao978318542

2018-03-22 12:33:08 +08:00

<?php
//悄悄的进村---------
$a=array(1,2,3,4,5);
$num=count($a)-1;
foreach($a as $key=>$b){
$x=$key+1;
foreach($a as $key2=>$c){
$y=$x+1;
if($x<=$num) {
foreach ($a as $d) {

if ($y <= $num) {

$aaa[]=array($b, $a[$x], $a[$y]);
}
$y++;
}
}
$x++;
}
}
print_r($aaa);die();
?>

dcalsky

2018-03-22 12:48:45 +08:00

neoblackcap

2018-03-22 13:30:01 +08:00

@kkzxak47

1. 你的推测只是你个人推测，并没有实据，编程是科学。所谓的找规律，我能找更多的满足题意但是是其他的规律。难道不可能推测最后一个元素限定是[3,4,5]这三个数字中的一个？
2. 你推测有额外的规则就是正常，难道我就不能推测题目有问题？这样就思维定式了？就算是面试也是允许询问的。题是人出的就会有错，这很正常的事情。

kkzxak47

2018-03-22 15:40:33 +08:00 via Android

@neoblackcap 目瞪狗呆。你赢了啊，八辈子都赢了。

shihty5

2018-03-22 16:05:55 +08:00

@RicardoScofileld 楼主快出来把题目说清楚

liqueur

2018-03-22 16:49:30 +08:00

N = [1, 2, 3, 4, 5]
M = 3
'''
output = [{1,2,3}{1,2,4},{1,2,5},{2,3,4},{2,3,5}{3,4,5}]
'''

output = []

for ix, x in enumerate(N):
for iy, y in enumerate(N[ix + 1:]):
for iz, z in enumerate(N[iy + 1:]):
if(y - x) == 1 and z > y:
output.append({x, y, z})

print(output)

liqueur

2018-03-22 16:50:15 +08:00

@liqueur 哇 v2 的代码支持不行啊

zacard

2018-03-22 17:16:32 +08:00

回溯法。

https://gist.github.com/mmaxiaolei/6bc4f3fe9432086eab1b690d3dde9d29

juicy

2018-03-22 17:24:18 +08:00

题目只有一条测试用例么，那一句 if..else..就可以了。。

sikariba

2018-03-22 17:59:03 +08:00

坐等楼主出来改题目

yidinghe

2018-03-22 18:59:29 +08:00

我这刚好昨天写了个组合遍历：
https://segmentfault.com/a/1190000013899418

虽然语言是 Java，但思路写在里面了：通过将解集看作树节点来遍历，而不是递归，可以做到：

1. 内存使用较小，因为只存储一个解；
2. 因为是在遍历树节点，所以可以从任何一个解开始遍历，或者叫“断点续历（？）”
3. 通过对树节点进行分派，可以实现多线程并发遍历。

MeteorCat

2018-03-22 19:02:11 +08:00 via Android

暴力穷举，无需动脑，上去就是莽

wwww961h

2018-03-22 19:19:58 +08:00

直接随机数组下标，然后排除重复，走 1000 次，不怕出不来，

Betsy

2018-03-22 20:25:22 +08:00 via Android

阿里的实习面试？

cs5791393

2018-03-23 08:53:13 +08:00

swfit

func arrangement(index: Int, arr: Array<String>) {
for i in index ... list.count-1{
let newArr = arr + [list[i]]
if newArr.count >= m{
print(newArr)
}else if i+1 < list.count{
arrangement(index:i+1,arr: newArr)
}
}
}

lepig

2018-03-23 09:17:55 +08:00

楼主放完题就不来关注回复了。简直没诚意请教。楼下都散了吧

zhijian

2018-03-23 10:27:48 +08:00

c#代码：

private static void Main(string[] args)
{
var m = new List<int> {1, 2, 3, 4, 5};
var result = new List<string>();
GetResult(m, ref result);
Console.Read();
}

private static void GetResult(List<int> m, ref List<string> result)
{
for (var i = 0; i < m.Count - 2; i++)
{
for (var k = i + 2; k < m.Count; k++)
{
result.Add(string.Format("{0},{1},{2}", m[i], m[i + 1], m[k]));
}
}
}

titachi

2018-03-23 11:39:33 +08:00

```python
def req(seq, m, idx=1):
n = len(seq)
sidx = idx - 1
eidx = m + sidx - 1
if m > n or n - sidx < m:
raise '大于 list 长度'
l, t = [], []
while eidx < n:
for i in seq[eidx:]:
l = seq[sidx:eidx]
l.append(i)
t.append(l)
sidx = sidx + 1
eidx = eidx + 1
return t

if __name__ == '__main__':
print(req([1, 2, 3, 4, 5], 3))

```

xpresslink

2018-03-23 17:59:51 +08:00

这么简单的一道题还用这么费劲。
算法是：
（ 1 ）取列表前两个元素依次和剩余每个元素组合
（ 2 ）递归下一次，列表取第一个元素后面部分按步骤（ 1 ）执行
（ 3 ）结束条件：列表剩三个元素直接返回列表

def solution(n, m):
□□□□if len(n) == m:
□□□□□□□□return [n]
□□□□else:
□□□□□□□□return [n[:2] + [i] for i in n[2:]] + solution(n[1:], m)

N=[1,2,3,4,5]
M=3

print(solution(N, M))
# [[1, 2, 3], [1, 2, 4], [1, 2, 5], [2, 3, 4], [2, 3, 5], [3, 4, 5]]

xpresslink

2018-03-23 18:08:31 +08:00

上面的给写死了，应该是按 M 可以变的
https://paste.ubuntu.com/p/jtnHCJmFp5/

def solution(n, m):
□□□□if len(n) == m:
□□□□□□□□return [n]
□□□□else:
□□□□□□□□return [n[:m-1] + [i] for i in n[m-1:]] + solution(n[1:], m)

N=[1,2,3,4,5]
M=3

print(solution(N, M))
# [[1, 2, 3], [1, 2, 4], [1, 2, 5], [2, 3, 4], [2, 3, 5], [3, 4, 5]]

RicardoScofileld

2018-03-25 21:59:29 +08:00

@acros 135 是可以的我没列出来就是数学中的组合

RicardoScofileld

2018-03-25 22:04:57 +08:00

@lepig 抱歉这两天有事都没上