Here's a fairly long but correct (as far as I can tell from the question discussion) implementation using recursion.
Important points:
- I iterate through both lists using
.pop(index). This lets me use recursion, as both lists get smaller and smaller as the function recurs, leading to a point where one list is of len(0).
- Numbers can be chosen from either list, and there is no limit to the numbers that can be chosen in a row from a single list.
- No consecutive duplicates are allowed.
- When comparing two non-equal digits, the smaller digit ALWAYS goes in the larger place. 23xxx is always lower than 32xxx.
Basically, if I have something like [1,2,3] and then [6,0,4], all of the digits in the first list will be before the first digit in the second list because 1236xx will ALWAYS be less than 6xxxxx, 1236xx less than 16xxxx, and 1236xx less than 126xxx, regardless of the values chosen for x.
z = [None]
#set to None so that z[-1] doesn't throw an out-of-range error
def small_list(a,b): #recursive function
### BASE CASE ###
if len(a) == 0: #if one list empty, can only add rest of other list
for i in b:
if i != z[-1]: #account for duplicates
z.append(i)
# else: #don't add duplicates
return z.pop(0) #end recursion, remove extraneous None
elif len(b) == 0: #if one list empty, can only add rest of other list
for j in a:
if j != z[-1]:#account for duplicates
z.append(j)
# else: #don't add duplicates
return z.pop(0) #end recursion, remove extraneous None
#Otherwise, we need to check whichever is smaller.
#The smaller number should ALWAYS go in the larger place (tens,hundreds,etc.) to make a smaller number.
### RECURSIVE CASE ###
if a[0] < b[0]:
if a[0] != z[-1]:
z.append(a.pop(0))
else:
a.pop(0)
elif a[0] > b[0]:
if b[0] != z[-1]:
z.append(b.pop(0))
else:
b.pop(0)
elif a[0] == b[0]:
a.pop(0)
small_list(a,b) # recur
Examples:
z = [None]
l1 = [1,2,3,2]
l2 = [2,1,1,1]
small_list(l1,l2)
print z
This first example prints [1, 2, 1, 3, 2] which is now correct.
z = [None]
l1 = [1,2,3]
l2 = [4,5,6]
small_list(l1,l2)
print z
This second example prints [1, 2, 3, 4, 5, 6] which is also now correct.
Here's the flow of how it computes the example you give above:
# The format is: [final list] len(a) [list a] len(b) [list b]
[] len(a) = 6 [3, 4, 5, 7, 9, 2] len(b) = 6 [3, 5, 7, 4, 2, 8]
# 3 repeated, so remove it.
[] len(a) = 5 [4, 5, 7, 9, 2] len(b) = 6 [3, 5, 7, 4, 2, 8]
# add lower of first two indices to final (4 v 3), and remove from corresponding list
[3] len(a) = 5 [4, 5, 7, 9, 2] len(b) = 5 [5, 7, 4, 2, 8]
# add lower of first two indices to final (4 v 5), and remove from corresponding list
[3, 4] len(a) = 4 [5, 7, 9, 2] len(b) = 5 [5, 7, 4, 2, 8]
# 5 repeated, so remove it.
[3, 4] len(a) = 3 [7, 9, 2] len(b) = 5 [5, 7, 4, 2, 8]
# add lower of first two indices to final (7 v 5), and remove from corresponding list
[3, 4, 5] len(a) = 3 [7, 9, 2] len(b) = 4 [7, 4, 2, 8]
# 7 repeated, so remove it.
[3, 4, 5] len(a) = 2 [9, 2] len(b) = 4 [7, 4, 2, 8]
# add lower of first two indices to final (9 v 7), and remove from corresponding list
[3, 4, 5, 7] len(a) = 2 [9, 2] len(b) = 3 [4, 2, 8]
# add lower of first two indices to final (9 v 4), and remove from corresponding list
[3, 4, 5, 7, 4] len(a) = 2 [9, 2] len(b) = 2 [2, 8]
# add lower of first two indices to final (9 v 2), and remove from corresponding list
[3, 4, 5, 7, 4, 2] len(a) = 2 [9, 2] len(b) = 1 [8]
# add lower of first two indices to final (9 v 8), and remove from corresponding list
[3, 4, 5, 7, 4, 2, 8] len(a) = 2 [9, 2] len(b) = 0 []
# list b is empty, add first element of list a (if non-duplicate)
[3, 4, 5, 7, 4, 2, 8, 9] len(a) = 1 [2] len(b) = 0 []
# list b is empty, add first element of list a (if non-duplicate)
#Finally:
[3, 4, 5, 7, 4, 2, 8, 9, 2]
