Inserting a value into all possible locations in a list

I am trying to do print all the possible outcomes o开发者_JS百科f a given list and I was wondering how to put a value into various locations in the list. For example, if my list was [A, B], I want to insert X into all possible index of the list such that it would return this [X, A, B], [A, X, B], [A, B, X].

I was thinking about using range(len()) and a for loop but not sure how to start.

---

Use insert() to insert an element before a given position.

For instance, with

arr = ['A','B','C']
arr.insert(0,'D')

arr becomes ['D','A','B','C'] because D is inserted before the element at index 0.

Now, for

arr = ['A','B','C']
arr.insert(4,'D')

arr becomes ['A','B','C','D'] because D is inserted before the element at index 4 (which is 1 beyond the end of the array).

However, if you are looking to generate all permutations of an array, there are ways to do this already built into Python. The itertools package has a permutation generator.

Here's some example code:

import itertools
arr = ['A','B','C']
perms = itertools.permutations(arr)
for perm in perms:
    print perm

will print out

('A', 'B', 'C')
('A', 'C', 'B')
('B', 'A', 'C')
('B', 'C', 'A')
('C', 'A', 'B')
('C', 'B', 'A')

---

You could do this with the following list comprehension:

[mylist[i:] + [newelement] + mylist[:i] for i in xrange(len(mylist),-1,-1)]

With your example:

>>> mylist=['A','B']
>>> newelement='X'
>>> [mylist[i:] + [newelement] + mylist[:i] for i in xrange(len(mylist),-1,-1)]
[['X', 'A', 'B'], ['B', 'X', 'A'], ['A', 'B', 'X']]

---

If you want to insert a list into a list, you can do this:

>>> a = [1,2,3,4,5]
>>> for x in reversed(['a','b','c']): a.insert(2,x)
>>> a
[1, 2, 'a', 'b', 'c', 3, 4, 5]

---

Simplest is use list[i:i]

    a = [1,2, 3, 4]
    a[2:2] = [10]

Print a to check insertion

    print a
    [1, 2, 10, 3, 4]

---

Coming from JavaScript, this was something I was used to having "built-in" via Array.prototype.splice(), so I made a Python function that does the same:

def list_splice(target, start, delete_count=None, *items):
    """Remove existing elements and/or add new elements to a list.

    target        the target list (will be changed)
    start         index of starting position
    delete_count  number of items to remove (default: len(target) - start)
    *items        items to insert at start index

    Returns a new list of removed items (or an empty list)
    """
    if delete_count == None:
        delete_count = len(target) - start

    # store removed range in a separate list and replace with *items
    total = start + delete_count
    removed = target[start:total]
    target[start:total] = items

    return removed

---

Just for fun, a solution that:

1. Allows inserting multiple values into all possible locations, not just one, and
2. Minimizes temporaries
3. Does not invoke O(n * m) work on the insertions (which naïve repeated calls to list.insert would perform)

Bonus, (for the person who asked a duplicate question) it makes use of the itertools module without it feeling completely forced:

import itertools

l1 = ['a','b','c','d','f']
l2 = ['Z', 'Y']

combined_indices = range(len(l1)+len(l2))
iterators = itertools.cycle(l1), itertools.cycle(l2)

l3 = []
for positions in map(frozenset, itertools.combinations(combined_indices , len(l2))):
    l3.append([next(iterators[idx in positions]) for idx in combined_indices])

print(*l3, sep="\n")

Try it online!

which produces output of the form:

['Z', 'Y', 'a', 'b', 'c', 'd', 'f']
['Z', 'a', 'Y', 'b', 'c', 'd', 'f']
['Z', 'a', 'b', 'Y', 'c', 'd', 'f']
['Z', 'a', 'b', 'c', 'Y', 'd', 'f']
['Z', 'a', 'b', 'c', 'd', 'Y', 'f']
['Z', 'a', 'b', 'c', 'd', 'f', 'Y']
['a', 'Z', 'Y', 'b', 'c', 'd', 'f']
['a', 'Z', 'b', 'Y', 'c', 'd', 'f']
# ... eleven lines omitted ...
['a', 'b', 'c', 'd', 'Z', 'f', 'Y']
['a', 'b', 'c', 'd', 'f', 'Z', 'Y']

And for bonus fun, a version that inserts the elements of l2 in either order (and condenses the work to an absurdly complicated listcomp for funsies):

from itertools import cycle, permutations, repeat

l1 = ['a','b','c','d','f']
l2 = ['Z', 'Y']

combined_indices = range(len(l1)+len(l2))
i1next = cycle(l1).__next__

l3 = [[pos_to_l2[pos] if pos in pos_to_l2 else i1next() for pos in combined_indices]
      for pos_to_l2 in map(dict, map(zip, permutations(combined_indices, len(l2)), repeat(l2)))]

print(*l3, sep="\n")

Try it online!

which behaves the same, but produces outputs where the elements of l2 are inserted in either order (when l2[0] shifts right, the other elements of l2 are inserted before it before they continue inserting after it, as in the first solution, e.g. the output sequence:

...
['Z', 'a', 'b', 'c', 'd', 'f', 'Y']
['a', 'Z', 'Y', 'b', 'c', 'd', 'f']
...

expands to:

...
['Z', 'a', 'b', 'c', 'd', 'f', 'Y']
['Y', 'Z', 'a', 'b', 'c', 'd', 'f']  # New
['a', 'Z', 'Y', 'b', 'c', 'd', 'f']
...

---

If l is your list and X is your value:

for i in range(len(l) + 1):
    print l[:i] + [X] + l[i:]