CODEWITHSUNDEEP
pythonlist
Paul
Paul

Reputation: 19

All the combinations without using itertools?

I want to know how to write an algorithm that gives me all the possible combinations of a list of numbers with repetition & without using itertools in Python.

For example: all possible combinations of the list [1,2]:

[[1,1],[1,2],[2,2],[2,1]]

All possible combinations of the list [1,2,3]. The algorithm will then give me 27 (33) different lists in a list.

This was my code:

def all_possibilities(list):
    result = [list]

    for i in list:
        new_list1 = list[:]

        for k in range(len(list)):
            new_list2 = list[:]
            new_list1[k] = i
            new_list2[k] = i
            if new_list1 != list:
                result.append(new_list1)
            if new_list2 != list:
                result.append(new_list2)

    for u in result:
        for y in result:
            if u == y and (u is y) == False:
                result.remove(y)

    return (len(result),result)

Upvotes: 0

Views: 2412

Answers (2)

Xero Smith
Xero Smith

Reputation: 2076

Here this actually does the combinations with replacement. You can adjust the size of the combinations. I made it return a tuple because tuples are immutable and tuple operations are faster than list operations. you can however easily make it return a list of list if you want. Cheers

def seq_slicer(container, step=10):
    """(container)->container
    Returns slices of container in chunks of step.
    Great selecting chunks of a sequence in predetrmined slices efficiently.

    In the event where step is greater than the length of the sequence to be sliced,
    the slice taken will be the length of the sequence.

    >>> [i for i in seq_slicer(range(40), 10)]
    [range(0, 10), range(10, 20), range(20, 30), range(30, 40)]

    >>> [i for i in seq_slicer(range(41), 10)]
    [range(0, 10), range(10, 20), range(20, 30), range(30, 40), range(40, 41)]

    >>> [c for c in seq_slicer("abcdefghijklm", 3)]
    ['abc', 'def', 'ghi', 'jkl', 'm']

    >>> [c for c in seq_slicer(list("abcdefghijklm"), 3)]
    [['a', 'b', 'c'], ['d', 'e', 'f'], ['g', 'h', 'i'], ['j', 'k', 'l'], ['m']]

    Author: Xero
    License: Apache V2
    """
    i = 0
    span = len(container)
    while i < span:
        yield container[i:i+step]
        i += step

def combinations_with_replacement(seq, num):
    """(sequence type, integer)->list
    return every possible combination of num elements from seq in lexicographic order
    >>> combinations_with_replacement([1, 2], 2)
    ((1, 1), (1, 2), (2, 1), (2, 2))


    Author: Xero
    License: Apache V2
    """
    lst = []
    _seq = tuple(seq)
    slices = [c for c in seq_slicer(_seq, num-1)]
    for elem in seq:
        for combo in [(elem,) + body for body in slices]:
            lst.append(combo)
    return tuple(lst)

Upvotes: 1

Mihai Alexandru-Ionut
Mihai Alexandru-Ionut

Reputation: 48357

You can write your own product method which finds out the cartesian product of multiple lists.

def cartesian_product(*lists):
  result = [[]]
  for list in lists:
    result = [x + [y] for x in result for y in list]
  return result  
l = [1, 2, 3]
lst = [l for i in l]
x = cartesian_product(*lst)
for tuple in x:
   print(tuple)

Output

(1, 1)
(1, 2)
(2, 1)
(2, 2)

Upvotes: 2

Related Questions