-1

I have two lists

[1, 3, 4] [7, 8]

I want to generate all the combinations of two list starting from the smallest combinations like 17,18,37,38,47,48,137,138,147,148......178,378.... Now for each combination I have to test it's presence in some other place and if I found that combination to be present then I will stop the combination generation. For example If I see that 17 is present then I will not generate the other combinations. Again If I found 48 to be present then I will not generate the later combinations.

mechanical_meat
  • 163,903
  • 24
  • 228
  • 223
tanay
  • 468
  • 5
  • 16
  • 1
    We don't do your homework for you. – Robert Columbia Jul 25 '16 at 17:04
  • 1
    If you want help with a homework problem (which I'm guessing is what this is), make sure to include what you've done so far and ask for advice, not solutions. I would recommend reading this: http://meta.stackexchange.com/questions/10811/how-do-i-ask-and-answer-homework-questions or this: http://meta.stackoverflow.com/questions/253792/stack-overflow-and-homework-questions – Checkmate Jul 25 '16 at 17:11
  • it's not a homework. It's part of a project I am doing. I need to generate all the combinations from the two list one by one. I was just asking is there any efficient way to do it as the one I am doing is not efficient... – tanay Jul 25 '16 at 17:11
  • 1
    @tanay fair enough then. Could you post the code you have so far? – Checkmate Jul 25 '16 at 17:12
  • Also, in your example, you give two lists that are already sorted. Can the initial two lists being presorted be assumed? – Checkmate Jul 25 '16 at 17:15
  • Oh, and also, could you just concatenate the second list to the first list and use: http://stackoverflow.com/questions/2710713/algorithm-to-generate-all-possible-permutations-of-a-list – Checkmate Jul 25 '16 at 17:17
  • Yes they will be sorted like the example. The reason I don't want to concatenate it because both the list belongs to different groups. I want the combination between the groups and not withing the group. I had the same soln as in the example but then I have to remove the combinations which are made within the group... – tanay Jul 25 '16 at 17:26
  • Wait, but wouldn't that make the 148 in your example invalid (two values from the first group, one from the second)? How many values can you take from each list? – Checkmate Jul 25 '16 at 17:28
  • Or are you saying you just require that elements from the first list must come before elements in the second list? – Checkmate Jul 25 '16 at 17:29
  • so combination of 13,14,34...78,.... will be invalid but not 137,348,1478.....As long as I have combination which covers both the list I am fine. But the length of the generated item must be in ascending order ie 17,18,38,....178 is fine but 17,18,178,...37 is not correct... – tanay Jul 25 '16 at 17:35
  • Let us [continue this discussion in chat](http://chat.stackoverflow.com/rooms/118247/discussion-between-checkmate-and-tanay). – Checkmate Jul 25 '16 at 17:38

1 Answers1

3

This is a pretty ugly algorithm, but it worked for me. It's also not super expensive (expect, of course, for generating all the combinations with itertools.combinations(a, i)...):

import itertools

def all_combs(a):
    to_return = []
    temp = []
    for i in a:
        temp.append(i)
    to_return.append(temp)
    for i in range(2, len(a) + 1):
        temp = []
        for j in itertools.combinations(a, i):
            s = ""
            for k in j:
                s = s + str(k)
            temp.append(int(s)) #Get all values from the list permutation
        to_return.append(temp)
    print(to_return)
    return to_return

def all_perm(a, b):
    a_combs = all_combs(a)
    b_combs = all_combs(b)
    to_return = []
    for i in a_combs:
        for j in b_combs:
            for k in i:
                for l in j:
                    to_return.append(10**len(str(l)) * k + l)
    to_return.sort()
    for i in to_return:
        yield i

EDIT: Fixed a bug where multi-digit values weren't read in correctly EDIT: Made the function act as a generator EDIT: Fixed a bug involving digits (by adding a sort...)

EDIT: Here's a vastly superior implementation which meets the generator style much more closely. It's still not perfect, but it should provide good speedup in the average case:

import itertools

def add_to_dict(dict, length, num):
    if not length in dict:
        dict[length] = []
    dict[length].append(num)

def sum_to_val(val):
    to_return = []
    for i in range(1, val):
        to_return.append([i, val-i])
    return to_return

def all_combs(a):
    to_return = {}
    for i in a:
        add_to_dict(to_return, len(str(i)), i)
    for i in range(2, len(a) + 1):
        for j in itertools.combinations(a, i):
            s = ""
            for k in j:
                s = s + str(k)
            add_to_dict(to_return, len(s), int(s)) #Get all values from the list permutation
    return to_return

def all_perm(a, b):
    a_combs = all_combs(a)
    b_combs = all_combs(b)
    for val in range(max(a_combs.keys())+max(b_combs.keys())+1):
        to_return = []
        sums = sum_to_val(val)
        for i in sums:
            if not(i[0] in a_combs and i[1] in b_combs):
                continue
            for j in a_combs[i[0]]:
                for k in b_combs[i[1]]:
                    to_return.append(10**len(str(k)) * j + k)
        to_return.sort()
        for i in to_return:
            yield i
Checkmate
  • 1,074
  • 9
  • 16
  • @tanay You may have found this already, but this code has a bug. I added a sort() to fix it, but this might be slow for large lists. I'll find a better solution. – Checkmate Jul 25 '16 at 19:47
  • Hmm, after testing, the time needed to put all the values in to_return and sort it is pretty unacceptable. Let me know if it's a problem for you and I can rewrite the algorithm to avoid this. – Checkmate Jul 25 '16 at 20:08
  • Sorry for late reply.. I actually modified a bit of the algorithm. I didn't want to pre-produce all the combinations of the two list before hand as If I get a match of the combination then I will stop looping. So I am only pre-producing for one list and then going through the other list and generating the combination as required. And when I get a match combination i stop there.. – tanay Jul 26 '16 at 18:12
  • Yeah, that works too. I'm guessing it will be slower than my updated algorithm, but if it's fast enough for your purposes, then that's what matters. – Checkmate Jul 26 '16 at 19:22
  • Why do u think it will be slower... I want to explain the thing more to u...suppose I have two list usr=[1,3,4] and obj=[7,8]. Now first I am creating all the combination of the list usr...so i am getting 1,3,4,13,14,34,134. Now for each value of the combination i am creating a combination of obj list on the fly and try to see that is the mergered combination(from usr and obj) is present somewhere or not. If it's present then I am done and in this way I don't have to pre-populate obj combination. – tanay Jul 26 '16 at 22:29
  • I'm going to go back to the chat room here: https://chat.stackoverflow.com/rooms/118247/discussion-between-checkmate-and-tanay – Checkmate Jul 26 '16 at 22:33