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

推荐学习书目

› Learn Python the Hard Way

Python Sites

› PyPI - Python Package Index

› http://diveintopython.org/toc/index.html

› Pocoo

值得关注的项目

› PyPy

› Celery

› Jinja2

› Read the Docs

› gevent

› pyenv

› virtualenv

› Stackless Python

› Beautiful Soup

› 结巴中文分词

› Green Unicorn

› Sentry

› Shovel

› Pyflakes

› pytest

Python 编程

› pep8 Checker

Styles

› PEP 8

› Google Python Style Guide

› Code Style from The Hitchhiker's Guide

This topic created in 3149 days ago, the information mentioned may be changed or developed.

需求是从数组 N 中获取长度为 M 的集合 example N = [1,2,3,4,5] M=3, 那么输出为 [{1,2,3}{1,2,4},{1,2,5},{2,3,4},{2,3,5}{3,4,5}]

example

求教

算法

集合

54 replies • 2018-03-25 22:04:57 +08:00

264768502

Mar 21, 2018 via Android

itertools groupby

siyemiaokube

Mar 21, 2018 via iPhone

排列组合都不会吗。。

siyemiaokube

Mar 21, 2018 via iPhone

一个数字标记数字的使用情况，然后搜索即可

264768502

Mar 21, 2018 via Android

itertools 的 combinations 就够了

acros

Mar 21, 2018

如果只能有序，为啥 1、3、5 不行？

xiaol825

Mar 21, 2018

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

Mar 21, 2018

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

lance6716276

Mar 21, 2018 via Android

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

whoami9894

Mar 21, 2018 via Android

@gclove 对呀 1.3.4 为啥也不行

junkiedon

Mar 22, 2018

DFS

kunluanbudang

Mar 22, 2018

把自己在 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

Mar 22, 2018

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

kkzxak47

Mar 22, 2018 via Android

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

neoblackcap

Mar 22, 2018

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

ujued

Mar 22, 2018 via iPhone

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

kkzxak47

Mar 22, 2018 via Android

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

neoblackcap

Mar 22, 2018

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

markx

Mar 22, 2018

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

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

markx

Mar 22, 2018

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

VincentBu

Mar 22, 2018

典型的 backtracking 题目

pyufftj

Mar 22, 2018

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

Hopetree

Mar 22, 2018

为什么不是 [{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

Mar 22, 2018

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

rebeccaMyKid

Mar 22, 2018

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

:D

faceRollingKB

Mar 22, 2018

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

crane2018

Mar 22, 2018

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

cs5791393

Mar 22, 2018

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

di94sh

Mar 22, 2018

``` 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

Mar 22, 2018

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

UnknownR

Mar 22, 2018

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

mathzhaoliang

Mar 22, 2018

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

kkzxak47

Mar 22, 2018 via Android

@neoblackcap

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

yao978318542

Mar 22, 2018

<?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

Mar 22, 2018

neoblackcap

Mar 22, 2018

@kkzxak47

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

kkzxak47

Mar 22, 2018 via Android

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

peterontheway

Mar 22, 2018

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

liqueur

Mar 22, 2018

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

Mar 22, 2018

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

zacard

Mar 22, 2018

回溯法。

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

juicy

Mar 22, 2018

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

sikariba

Mar 22, 2018

坐等楼主出来改题目

yidinghe

PRO

Mar 22, 2018

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

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

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

MeteorCat

Mar 22, 2018 via Android

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

wwww961h

Mar 22, 2018

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

Betsy

Mar 22, 2018 via Android

阿里的实习面试？

cs5791393

Mar 23, 2018

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

Mar 23, 2018

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

zhijian

Mar 23, 2018

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

Mar 23, 2018

```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

Mar 23, 2018

这么简单的一道题还用这么费劲。
算法是：
（ 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

Mar 23, 2018

上面的给写死了，应该是按 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

Mar 25, 2018

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

RicardoScofileld

Mar 25, 2018

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