All the combinations without using itertools?

Question

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 (3³) 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)

what specific problem are you having with the implementation? — Paul H
– Paul H, Commented May 5, 2018 at 14:05
If you are looking for pure python equivalent of itertools.permutations you can check the implementation of this method is docs — Sohaib Farooqi
– Sohaib Farooqi, Commented May 5, 2018 at 14:09
I know the concept of recursion but I've tried writing it multiple times and I never get ALL the possible solutions. — Paul
– Paul, Commented May 5, 2018 at 14:20

Mihai Alexandru-Ionut · Accepted Answer · 2018-05-05 14:27:07Z

2

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)

edited May 5, 2018 at 14:27

answered May 5, 2018 at 14:13

Mihai Alexandru-Ionut

48.6k14 gold badges106 silver badges132 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

roganjosh Over a year ago

"WITHOUT using itertools" was in the question

Paul Over a year ago

@MihaiAlexandru-Ionut can you explain what happens on line 4 please? Thanks in advance

Mihai Alexandru-Ionut Over a year ago

@PaulvanTieghem, basically it created a list [[1],[2],[3]] then [[1, 1], [1, 2], [1, 3], [2, 1], [2, 2], [2, 3], [3, 1], [3, 2], [3, 3]] and so on.

Xero Smith · Accepted Answer · 2018-05-05 14:40:28Z

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)

@PaulvanTieghem, your'e welcome. Please mark the answer as accepted and upvote if it works for you and you find it useful
@XeroSmith, upvote for your answer. I know the feeling when write a long and correct answer and nobody upvotes it in order to recognize the effort and time invested into answering the question.

Collectives™ on Stack Overflow

All the combinations without using itertools?

2 Answers 2

3 Comments

3 Comments

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

3 Comments

3 Comments

Linked

Related