All possible combinations that differ by "N" elements in Python-CodePudding

I am looking for a simple way to find all possible ways to switch Nelements between two lists list1 and list2, such that the new lists list1' differ from list1 by N elements. The two lists will not have common elements (they contain a set of indices, to be more exact). It is the set of all possible list1' I need.

Now, I want a function that takes list1, list2 and N as parameters, and returns all possible lists where N elements have been replaced. The order of elements in each list is not important.

For example, using N=1, list1=[0,1],list2=[2,3], I would want to get: [([0,2],[1,3]),([0,3],[2,1]),([2,1],[0,3]),([3,1],[2,0])], and using N=2, I woul want to get [([2,3],[0,1])].

My initial idea was to use itertools.combinations(list1 list2,len(list1)) and then discard all those elements that differ by more than N elements. This works in principle, but the problem is that list1 and list2 are rather long, hence creating all combinations is excessive and time-demanding, while N will be some value between 1 and 4.

I would not mind a scipy/numpy-solution, using arrays instead of lists.

PS: In case someone wonders, this is for quantum chemistry - I want to find all possible excited slater determinants, replacing N occupied MOs with virtual MOs. So if someone knows of a solution in for example pyscf, that would be great, too!

CodePudding user response：

I could solve the case for N=1 at the moment. I don't think you need combinations but product to generalize for any N.

def paring(l1, l2):
    partitions = []
    for i1, v1 in enumerate(l1):
        for i2, v2 in enumerate(l2):
            partitions  = [(l1[:i1]   [v2]   l1[i1 1:], l2[i2 1:]   [v1]   l2[:i2])]
    return partitions


def list2string(mylist):
    print('\n'.join([''.join(p[0])   ' '   ''.join(p[1])  for p in mylist]))


list2string(paring(['a1', 'a2'], ['b1', 'b2', 'b3']))

Output

b1a2 b2b3a1
b2a2 b3a1b1
b3a2 a1b1b2
a1b1 b2b3a2
a1b2 b3a2b1
a1b3 a2b1b2

CodePudding user response：

Rather than generate all possible combinations and filter after, you can track what swaps have already been made so that duplicate recursive calls are eliminated:

import copy
def swaps(d, s_w):
   if not s_w:
      yield tuple([tuple([k[1] if isinstance(k, tuple) else k for k in b]) for b in d])
   else:
      for i, a in enumerate(d):
        for j, k in enumerate(a):
           if not isinstance(k, tuple):
              for x, y in ((x, y) for x, m in enumerate(d) for y, t in enumerate(m) if not isinstance(t, tuple) and x != i):
                  _d = copy.deepcopy(d)
                  _d[i][j] = (True, _d[x][y])
                  _d[x][y] = (True, k)
                  yield from swaps(_d, s_w - 1)

n, n2, list1, list2 = 1, 2, [0,1], [2,3]
r = [*set(swaps([list1, list2], n))]
r1 = [*set(swaps([list1, list2], n2))]

Output:

[((3, 1), (2, 0)), ((0, 2), (1, 3)), ((2, 1), (0, 3)), ((0, 3), (2, 1))]
[((2, 3), (0, 1)), ((3, 2), (1, 0))]