求个随机整数的 算法

Question

从1到100的整数中随机10个，然后和为100的组合有哪些？

Answer 1

根据题主断句方式，倾向于从1到100中随机10个数，然后求出10个随机数中和为100的组合。
那么

import random
from itertools import combinations

rd = random.sample(range(1, 101), 10)
# 10个数的组合不多，简单暴力点
comb = [j for i in range(1, 11) for j in combinations(rd, i) if sum(j) == 100]
print(rd)
print(comb)

如果是100个数里求10个和为100的数的组合，组合情况比较多，暴力不可取。

def get_combs(n=100, k=10, tg=100):
    combs = []
    x = tg - sum(range(1, k))

    def dfs(comb, idx=0, k=k, t=tg):
        dmx = min(tg - sum(comb), x, n)
        arr = range(1, dmx + 1)
        if t == 0 and k == 0:
            combs.append(comb[:])
            return
        if dmx <= idx or k < 0 or t < 0:
            return
        for i in range(idx, dmx):
            v = arr[i]
            dfs(comb + [v], i + 1, k - 1, t - v)

    dfs([])

    return combs

Answer 2

# coding: utf-8

import random

def combinationSum2(candidates, target):
    res = []
    can = sorted(candidates)

    def dfs(comb, s, i):
        while i < len(can):
            if can[i] + s > target:
                return
            elif can[i] + s == target:
                if (comb + [can[i]]) not in res:
                    res.append(comb + [can[i]])
            else:
                dfs(comb + [can[i]], s + can[i], i + 1)
            i += 1

    dfs([], 0, 0)
    return res

#从1-100之间随机10个数
lst = random.sample(range(1, 101), 10)
#找出随机数和为100的组合
print combinationSum2(lst, 100)

Answer 3

import itertools
[x for x in itertools.combinations(range(1, 101), 10) if sum(x) == 100]

直接用列表推导到方式是可以到，但是性能很低下，建议使用生成器。

Answer 4

--update3:
今天偶然挖坟，这道题我又想到了一个可以优化的地方，所以还是把改过的代码提出来，大家看还有没有进一步可以改进的

import itertools

"""
算法有两个重要的优化点:
    1. 组合中的最大BIGGEST有限制，也就是考虑前9个数和最小的情况
    2. 组合按生序排列的首元素有最大限制，首元素是我们递归试算的起始点
"""

BIGGEST = 100 - sum(range(1, 10))
MAX_HEAD = list(itertools.takewhile(lambda x:sum(x) <= 100, (range(1, 101)[i:i+10] for i in range(0, 100))))[-1][0]

def fetch(current, selected=[]):
    if current <= BIGGEST and len(selected) < 10:
        selected_ = selected + [current]
        sum_val = sum(selected_)
        n = len(selected_)
        if sum_val == 100 and n == 10:
            yield selected_
        elif sum_val < 100 and n < 10:
            for i in range(current+1, 100 - sum_val + 1):
                yield from fetch(i, selected_)
                
choices = [c for h in range(1, MAX_HEAD + 1) for c in fetch(h)]
for c in choices:
    print(','.join(str(i) for i in c))
    

--update2:
刚刚测试了一下 @dodopy 的代码，发现输出的解数量是33401，而我的只有25331，是我的错了，错得很明显，我只获取了‘1’开头的所有解。因为dodopy的算法很高效，所以我不改我的代码了，建议采纳 @dodopy 的答案。我写了一个验证脚本,test_c_100.py, 假定程序输出到result.txt, 每行是逗号分隔的10个数，代表一个解。这个脚本的运行方式 test_c_100.py result.txt. 希望对大家验证结果有帮助

test_c_100.py

#!/usr/bin/env python

import sys

def travel_result(filename, func):
    allpass = True
    with open(filename, 'r') as f:
        for line in f:
            success, msg = func(line)
            if not success:
                print(msg)
                allpass = False
    return allpass

def check_sum(line):
    numbers = [int(i) for i in line.split(',')]
    sum_v = sum(numbers)
    if sum_v == 100 and len(numbers) == 10:
        return True, ''
    else:
        return False, 'error! line: {l}, sum: {s}'.format(l=line, s=sum_v)

choices = []
def check_uniq(line):
    global choices
    c = {int(i) for i in line.split(',')}
    if len(c) != 10:
        return False, '"{l}" has not 10 uniq number'.format(line)
    elif c in choices:
        return False, '{c} repeated'.format(c)
    else:
        choices.append(c)
        return True, ''

filename = sys.argv[1]
if travel_result(filename, check_sum):
    print("Pass check sum test")
else:
    print("Not pass check sum test")

if travel_result(filename, check_uniq):
    print("Pass check uniq test")
else:
    print("Not pass check uniq test")

--update:
把selected从set改成list省了三分之一运行时间

先贴一下我的代码，python3.6 环境运行

biggest = 100 - sum(range(1, 10))

def fetch(current=1, selected=[]):
    if current <= biggest and len(selected) < 10:
        selected_ = selected + [current]
        sum_val = sum(selected_)
        n = len(selected_)
        if sum_val == 100 and n == 10:
            yield selected_
        elif sum_val < 100 and n < 10:
            for i in range(current+1, biggest+1):
                yield from fetch(i, selected_)

choices = [i for i in fetch()]
print("number of choices: {}".format(len(choices)))
[print(i) for i in choices]

输出是

number of choices: 25331
[1, 2, 3, 4, 5, 6, 7, 8, 9, 55]
[1, 2, 3, 4, 5, 6, 7, 8, 10, 54]
...

@prolifes 我想你对题意中的“随机”两个字有误解
@藕丝空间 对题意的理解和解法都是对的，但是大家想想
itertools.combinations(range(1, 101), 10) 的元素有多少？ 100！/90！，还是应该找找可以优化的点的。

首先10个数里最大的数不会超过55， 因为选择前9个数选择最小的和也为45，这是第一个可以缩小问题规模的地方。

缩小规模到这一步，代码运行也很耗时。

另外我想到可以优化的点是，假设当前状态是你还剩下n个数没选，你已经选的10-n个数之和是s1, 待选集合中最小的n个数之和是s2, s1+s2>100 那么就不必再继续试了，退回上一步。这个优化我没实现，究竟能不能更优也是疑问，sorted未必必多递归几次省多少时间，我还没有深想。

这份代码还有一个问题是递归深度太大了，只是我觉得这样写更简明，有空再改一个非递归的版本

Answer 5

这不是随机，是排列组合了吧？