How to make this code work better (list of combinations)?

Question

import random

def ordenar(inputx):
    inputx = list(inputx)
    inputx = sorted(inputx, key=int)
    return inputx

def get_numbers(totall):
    return random.sample(numeros, totall)

numeros = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25]

all_jogos = []
maximo_repetido = 9

vezes = 0

while True:
    numbers = get_numbers(15)
    for i in all_jogos:
        total_repetido = len(set(numbers).intersection(i))
        if total_repetido <= maximo_repetido:
            vezes += 1
        else:
            vezes = 0
            break
    if vezes >= len(all_jogos):
        all_jogos.append(numbers)
        print("%s," % ordenar(numbers))

Basically my intention is to generate lists of 15 numbers, so that there are no more than 9 numbers repeated between them (variable maximo_repetido), generating as many lists as possible. The comparison is made with all the lists contained in all_jogos, which grows with each loop as long as the condition is accepted.

The problem is that all possible results can never occur, since validation / comparison is only done after generating 15 random numbers.

How do you make the condition / validation / comparison to be made when you are going to generate the numbers, forcing you to search for only the possible results?

Side-note: `ordenar` can and should simplify to just `return sorted(inputx)`; the inputs are already sequences of integers, so `key=int` is redundant, and `sorted` already converts to a new `list` before sorting, so manually constructing a list with `list()` just means an extra pointless temporary list. — ShadowRanger, Jun 02 '18 at 00:59

score 0 · Accepted Answer · answered Jun 02 '18 at 00:59

0

itertools.combinations(iterable, n) gives you all the n-length combinations of elements in iterable. That's what you want to use here.

import itertools

numbers = range(1, 26)

combos = itertools.combinations(numbers, 15)

combos is now an iterator (not a list, note, so if you need to read through it more than once you need to cast it explicitly) of all 15-length combinations of the numbers 1-25, and you can use A* or some other pathfinding algorithm to find the best possible solution.

answered Jun 02 '18 at 00:59

Adam Smith

52,157
12
73
112

note that there is *definitely* a mathematical solution for this that will run in constant time, but finding that solution is up to you! – Adam Smith Jun 02 '18 at 01:04
This code does not limit the maximum number of repeated items among all possible lists. (Maximum 9) – Geek Jun 02 '18 at 01:07
@Geek right -- that's part of the job of your pathfinding algorithm (not included here). This problem is generalized to "How can I find out what combination of an iterator maximizes a certain utility function." – Adam Smith Jun 02 '18 at 01:07
Thanks, but it still is not solution to my problem. I have no idea how to end your code to work as I wish, since I am a beginner in python. – Geek Jun 02 '18 at 01:13
@Geek here's a [sample implementation](https://stackoverflow.com/questions/4159331/python-speed-up-an-a-star-pathfinding-algorithm) of A* in Python. I'd prefer A* here since you have a pretty clear metric function (in general reducing the number of overlapping numbers per step will be better) – Adam Smith Jun 02 '18 at 01:14
1

Thank you, now I understand your idea :) – Geek Jun 05 '18 at 23:49

How to make this code work better (list of combinations)?

1 Answers1