0

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)
martineau
  • 119,623
  • 25
  • 170
  • 301
Paul
  • 19
  • 6
  • 2
    what specific problem are you having with the implementation? – Paul H May 05 '18 at 14:05
  • If you are looking for pure python equivalent of `itertools.permutations` you can check the implementation of this method is [docs](https://docs.python.org/3/library/itertools.html#itertools.permutations) – Sohaib Farooqi May 05 '18 at 14:09
  • The concept you will need to learn is recursion. – Alex Hall May 05 '18 at 14:13
  • I know the concept of recursion but I've tried writing it multiple times and I never get ALL the possible solutions. – Paul May 05 '18 at 14:20
  • 1
    show us what you've tried and show us how it fails. – Paul H May 05 '18 at 14:21
  • Welcome to SO. Unfortunately this isn't a discussion forum or tutorial service. Please take the time to read [ask] and the other links found on that page. – wwii May 05 '18 at 15:03
  • I suggest that you read the [`itertools.combinations()`](https://docs.python.org/3/library/itertools.html#itertools.combinations) documentation, which shows what it's roughly equivalent to in pure Python. – martineau May 05 '18 at 15:47

2 Answers2

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)
Mihai Alexandru-Ionut
  • 47,092
  • 13
  • 101
  • 128
1

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)
Xero Smith
  • 1,968
  • 1
  • 14
  • 19
  • Thanks a lot for your help! – Paul May 05 '18 at 14:46
  • @PaulvanTieghem, your'e welcome. Please mark the answer as accepted and upvote if it works for you and you find it useful – Xero Smith May 05 '18 at 14:48
  • 1
    @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. – Mihai Alexandru-Ionut May 05 '18 at 16:21