Python面试中遇到的一道算法题，求教
需求是从数组 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}]
Python面试中遇到的一道算法题，求教
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®)
yield tuple(pool[i] for i in indices)
while True:
for i in reversed(range®):
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)
把自己在 leetcode 上的垃圾代码粘贴一次
:)<br>class Solution:<br> def __init__(self, ):<br> self._res = []<br><br> def combine(self, n,k):<br> if (n <= 0) or (k <= 0) or (k > n):<br> return []<br> else:<br> c = []<br> self.generate_combinations(n, k, 1, c)<br> return self._res<br><br> def generate_combinations(self, n, k, start, c):<br> if len(c) == k:<br> self._res.append(copy.deepcopy(c))<br> return<br> else:<br> i = start<br> maxI = n - (k-len(c) )+ 1<br> while i <= maxI:<br> print(c)<br> c.append(i)<br> self.generate_combinations(n, k, i+1, c)<br> c.pop()<br><br> i += 1<br> return<br>
哈哈，当时面试的时候我也有类似的经历。当时让我统计某种特征最多的几个数，我当时使用 Counter 库，两行代码搞定，面试官都蒙了。不过肯定是让你实现底层代码，这样做面试官肯定不满意吧
为什么不是 [{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}]
python<br>def combination(numlist, m, low=0):<br> if m==0:<br> yield []<br> else:<br> for i in range(low, len(numlist)):<br> for rest in combination(numlist, m - 1, i + 1):<br> yield [numlist[i]] + rest<br><br>def combinations(numlist, m):<br> return list(combination(numlist, m))<br>numlist = [1, 2, 3, 4, 5]<br>print(combinations(numlist, 3))<br>
题目的输出样例是摆看的吗？
{1,2,3}{1,2,4},{1,2,5},
{2,3,4},{2,3,5}
{3,4,5}
为什么一旦题设不符合你的思维定势，就无所适从，真的不能稍微多想一点点吗？
<?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();
?>
<script src=“https://gist.github.com/dcalsky/b1925dc429a37d033eed71ff755b4271.js”></script>
1. 你的推测只是你个人推测，并没有实据，编程是科学。所谓的找规律，我能找更多的满足题意但是是其他的规律。难道不可能推测最后一个元素限定是[3,4,5]这三个数字中的一个？
2. 你推测有额外的规则就是正常，难道我就不能推测题目有问题？这样就思维定式了？就算是面试也是允许询问的。题是人出的就会有错，这很正常的事情。
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)
我这刚好昨天写了个组合遍历：
https://segmentfault.com/a/1190000013899418
虽然语言是 Java，但思路写在里面了：通过将解集看作树节点来遍历，而不是递归，可以做到：
1. 内存使用较小，因为只存储一个解；
2. 因为是在遍历树节点，所以可以从任何一个解开始遍历，或者叫“断点续历（？）”
3. 通过对树节点进行分派，可以实现多线程并发遍历。
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)
}
}
}
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]));
}
}
}
python<br>def req(seq, m, idx=1):<br> n = len(seq)<br> sidx = idx - 1<br> eidx = m + sidx - 1<br> if m > n or n - sidx < m:<br> raise '大于 list 长度'<br> l, t = [], []<br> while eidx < n:<br> for i in seq[eidx:]:<br> l = seq[sidx:eidx]<br> l.append(i)<br> t.append(l)<br> sidx = sidx + 1<br> eidx = eidx + 1<br> return t<br><br><br>if __name__ == '__main__':<br> print(req([1, 2, 3, 4, 5], 3))<br><br>
这么简单的一道题还用这么费劲。
算法是：
（ 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]]
上面的给写死了，应该是按 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]]
