Python given dict of old index: new index move multiple elements in a list

In Python 3 what would be the best way to move multiple potentially non-contiguous elements to new potentially non-contiguous indexes given a dict of {old index: new index, old index: new index, old index: new index}

Important Note: the dict may not contain all the new positions of elements, this is why the examples below the first example do not work

Edit: Sorry I forgot to mention that you don't have to worry about checking all the indexes in new_idxs are valid and within the bounds of seq. The keys of new_idxs are also already in sorted order

from typing import Any


def move_elements(
    seq: list[Any],
    new_idxs: dict,
) -> list[Any]:
    new = []
    idx = 0
    done = set()
    while len(new) < len(seq):
        if idx in new_idxs and idx not in done:
            new.append(seq[new_idxs[idx]])
            done.add(idx)
        elif idx not in done:
            new.append(seq[idx])
            idx += 1
        else:
            idx += 1
    return new


# works
new_idxs = {0: 1, 1: 0}
seq = [0, 1]
seq = move_elements(seq, new_idxs)
print ("\nexpected:", [1, 0])
print ("actual  :", seq)
# expected output
# [1, 0]

# doesn't work
new_idxs = {3: 0, 5: 1}
seq = [0, 1, 2, 3, 4, 5, 6, 7]
seq = move_elements(seq, new_idxs)
print ("\nexpected:", [3, 5, 0, 1, 2, 4, 6, 7])
print ("actual  :", seq)
# expected output
# [3, 5, 0, 1, 2, 4, 6, 7]

# doesn't work
new_idxs = {3: 6, 5: 7}
seq = [0, 1, 2, 3, 4, 5, 6, 7]
seq = move_elements(seq, new_idxs)
print ("\nexpected:", [0, 1, 2, 4, 6, 7, 3, 5])
print ("actual  :", seq)
# expected output
# [0, 1, 2, 4, 6, 7, 3, 5]

new_idxs = {3: 1, 7: 4}
seq = [0, 1, 2, 3, 4, 5, 6, 7]
seq = move_elements(seq, new_idxs)
print ("\nexpected:", [0, 3, 1, 2, 7, 4, 5, 6])
print ("actual  :", seq)
# expected output
# [0, 3, 1, 2, 7, 4, 5, 6]

new_idxs = {0: 3, 3: 1, 7: 4}
seq = [0, 1, 2, 3, 4, 5, 6, 7]
seq = move_elements(seq, new_idxs)
print ("\nexpected:", [1, 3, 2, 0, 7, 4, 5, 6])
print ("actual  :", seq)
# expected output
# [0, 1, 2, 3, 4, 5, 6, 7]
# [1, 3, 2, 0, 7, 4, 5, 6]

A linear time one. I start with a result list full of dummy objects. Then move elements from the input sequence into the result list as requested. Then replace the remaining dummies in the result with the remaining non-dummy elements from the input sequence.

from typing import Any


def move_elements(
    seq: list[Any],
    new_idxs: dict,
) -> list[Any]:

    dummy = object()
    res = [dummy] * len(seq)
    seq = seq[:]

    for old, new in new_idxs.items():
        res[new] = seq[old]
        seq[old] = dummy

    remaining = (x for x in seq if x is not dummy)
    for i, x in enumerate(res):
        if x is dummy:
            res[i] = next(remaining)

    return res


def test(seq, new_idxs, expect):
    result = move_elements(seq, new_idxs)
    print('seq:     ', seq)
    print('new_idxs:', new_idxs)
    print('expect:  ', expect)
    print('result:  ', result)
    print('correct? ', result == expect)
    print()

test([0, 1], 
     {0: 1, 1: 0},
     [1, 0])
test([0, 1, 2, 3, 4, 5, 6, 7],
     {3: 0, 5: 1},
     [3, 5, 0, 1, 2, 4, 6, 7])
test([0, 1, 2, 3, 4, 5, 6, 7],
     {3: 6, 5: 7},
     [0, 1, 2, 4, 6, 7, 3, 5])
test([0, 1, 2, 3, 4, 5, 6, 7],
     {3: 1, 7: 4},
     [0, 3, 1, 2, 7, 4, 5, 6])

Output (Attempt This Online!):

seq:      [0, 1]
new_idxs: {0: 1, 1: 0}
expect:   [1, 0]
result:   [1, 0]
correct?  True
seq:      [0, 1, 2, 3, 4, 5, 6, 7]
new_idxs: {3: 0, 5: 1}
expect:   [3, 5, 0, 1, 2, 4, 6, 7]
result:   [3, 5, 0, 1, 2, 4, 6, 7]
correct?  True
seq:      [0, 1, 2, 3, 4, 5, 6, 7]
new_idxs: {3: 6, 5: 7}
expect:   [0, 1, 2, 4, 6, 7, 3, 5]
result:   [0, 1, 2, 4, 6, 7, 3, 5]
correct?  True
seq:      [0, 1, 2, 3, 4, 5, 6, 7]
new_idxs: {3: 1, 7: 4}
expect:   [0, 3, 1, 2, 7, 4, 5, 6]
result:   [0, 3, 1, 2, 7, 4, 5, 6]
correct?  True

A solution:

def move_elements(
seq: list,
new_idxs: dict
) -> list:
result = [None] * len(seq)
for old, new in new_idxs.items():
result[new] = seq[old]
for val in seq:
res_idx = 0
while res_idx < len(seq) and result[res_idx] != None:
res_idx += 1
if res_idx == len(seq): return result
if val in result: continue
result[res_idx] = val
return result

Output (for your test cases):

[1, 0]
[3, 5, 0, 1, 2, 4, 6, 7]
[0, 1, 2, 4, 6, 7, 3, 5]
[0, 3, 1, 2, 7, 4, 5, 6]