Version 2 - print new even-length arrays from two arrays

Question

This is an update of the code for my previous post (which has now been removed as this code is more efficient and accurate) for the GeeksForGeeks task.

Task outline

Given two arrays, print all new arrays of even length where each subsequent element in the new array comes alternately from A then B and each element is larger than the previous element

Example:

• Array 1 = [1, 2, 3]
• Array 2 = [2, 4, 6]

Possible new array lengths = [2, 4, 6]

The output for arrays of length 2 is: [1,2], [1,4], [1,6], [2,4], [2,6], [3,4] [3,6]

The full solution for the above includes the following two additional arrays: [1 2 3 4], [1 2 3 6]

This solution uses the itertools library

import itertools
A=[10, 20, 30,40]
B=[11,21,31,41]
list_solutions = []
for x in range (1,min(len(A),len(B))+1):
 newA = list(itertools.combinations(A,x))
 newB = list(itertools.combinations(B,x))
 for itemA in newA:
 for itemB in newB:
 to_print = True 
 for index in range (min(len(itemA),len(itemB))):
 if itemA[index] >= itemB[index]: 
 to_print = False 
 break 
 if to_print == True: 
 list_solutions.append([itemA, itemB])
#Print only valid solutions:
for item in list_solutions:
 print_valid = True 
 for index in range (len(item[0])):
 if item[0][index] >= item[1][index]:
 print_valid = False 
 break 
 if index >= 1:
 if item[0][index] <= item[1][index-1]:
 print_valid = False
 break 
 if print_valid == True:
 for index in range (len(item[0])):
 print (item[0][index], item[1][index], sep = " ", end = " ")
 print ("")
 if print_valid == False:
 continue 

• MiniMax: Have you figure out the selector ^ 1 moment? I have added explanation to the answer.
• MrJoe: Yes thanks. I ran a few examples myself and worked it out. THanks for the update

Answer 1

Reference

When solving puzzles from websites, I always include the link and the task description. In case of Project Euler questions, this already helped me figure out that their tasks change over time. In your case, such a reference could look like

# https://www.geeksforgeeks.org/generate-all-possible-sorted-arrays-from-alternate-elements-of-two-given-arrays/
# Given two sorted arrays A and B, generate all possible arrays such that first element is taken from A then from B then from A and so on in increasing order till the arrays exhausted. The generated arrays should end with an element from B.

Redundant comparisons

In your code I see if xxx == True: which can be shortened to if xxx:. I wrote the same code as a beginner, so I guess it's absolutely normal.

Similarly, if xxx == False: would be written as if not xxx:.

An IDE like PyCharm will give you hints for such issues and even help you replace it by an equivalent.

Unnecessary continue statement

if print_valid == False:
 continue 

This part is unnecessary, since it's the last statement of the loop, so the loop would continue anyway.

Separate output from logic

Do the calculations on their own, then do all the printing. E.g. define a function which prints the lists as you like to:

def print_all(results: List) -> None:
 for result in results:
 for item in result:
 print(item, sep=" ", end=" ")
 print()

Type safety

You can from typing import *and use type hints to make clear what types are used. This is especially useful when using functions (see next section).

Use testable functions

Right now, you have some input which gives some output, but you don't have a test whether your code works for the given input. The website already indicates that there is a defined set of solutions for the given input A = {10, 15, 25}and B = {1, 5, 20, 30}.

You could implement it like this:

def get_potential_solutions() -> List:
 list_solutions = []
 ...
 return list_solutions = []
def filter_solutions(list_solutions: List) -> List:
 # Print only valid solutions:
 valid_results = []
 current_result = []
 for item in list_solutions:
 ...
 return valid_results
list_solutions = get_potential_solutions(A, B)
list_solutions = filter_solutions(list_solutions)
print_all(list_solutions)

You can then implement an assertion which will warn you whenever you broke your code.

givensolution = [[10, 20], [10, 30], [15, 20], [15, 30], [25, 30], [10, 20, 25, 30], [15, 20, 25, 30]]
solution = filter_solutions(get_potential_solutions([10, 15, 25], [1, 5, 20, 30]))
assert (solution == givensolution)

If you do this many times, read about unit tests.

Naming

I still didn't understand the algorithm you implemented. It may have to do with the terms x, item, index, newA and newB, itemA and itemB, which tell me nothing.

• x is used in itertools.combinations(), so it must be the length
• newA and newB are combinations, so I renamed them to combinationsA and combinationsB
• itemA and itemB are a specific combination, so I renamed them to combinationA and combinationB

You may say that this is not an improvement. I'd say I moved from a nonsense name to a honest name, which is at least one step better, but still on level 2 of the 6 stages of naming

Doubled condition

IMHO, the condition in get_potential_solutions()

if combinationA[position] >= combinationB[position]:
 valid = False
 break

is identical to the condition in filter_solutions()

if item[0][index] >= item[1][index]:
 valid = False
 break

Since it is about filtering, I'd prefer to remove it in the potentials method.

Make smaller methods

The check whether a potential solution is valid or not can be moved into its own method.

def is_valid_solution(potential):
 for index in range(len(potential[0])):
 if potential[0][index] >= potential[1][index]:
 return False
 if index >= 1:
 if potential[0][index] <= potential[1][index - 1]:
 return False
 return True

The next loop seems to just clean up the results in order to remove the tupels. This can be done in a method as well:

def flatten(potential):
 current_result = []
 for index in range(len(potential[0])):
 current_result.append(potential[0][index])
 current_result.append(potential[1][index])
 return current_result

Single responsibility

The filter_solutions() method now does 2 things: filtering and flattening. One could argue that this should be separated. And it's simple to do now.

Final result

import itertools
from typing import *
A = [10, 20, 30, 40]
B = [11, 21, 31, 41]
def get_potential_solutions(a: List, b: List) -> List:
 potentials = []
 for length in range(min(len(a), len(b))):
 combinationsA = list(itertools.combinations(a, length + 1))
 combinationsB = list(itertools.combinations(b, length + 1))
 for combinationA in combinationsA:
 for combinationB in combinationsB:
 potentials.append([combinationA, combinationB])
 return potentials
def filter_solutions(potentials: List) -> List:
 valid_results = []
 for potential in potentials:
 if is_valid_solution(potential):
 valid_results.append(potential)
 return valid_results
def is_valid_solution(potential):
 for index in range(len(potential[0])):
 if potential[0][index] >= potential[1][index]:
 return False
 if index >= 1:
 if potential[0][index] <= potential[1][index - 1]:
 return False
 return True
def flatten_list(solutions: List) -> List:
 result = []
 for solution in solutions:
 result.append(flatten(solution))
 return result
def flatten(potential):
 current_result = []
 for index in range(len(potential[0])):
 current_result.append(potential[0][index])
 current_result.append(potential[1][index])
 return current_result
def print_all(results: List) -> None:
 for result in results:
 for item in result:
 print(item, sep=" ", end=" ")
 print()
givensolution = [[10, 20], [10, 30], [15, 20], [15, 30], [25, 30], [10, 20, 25, 30], [15, 20, 25, 30]]
solution = flatten_list(filter_solutions(get_potential_solutions([10, 15, 25], [1, 5, 20, 30])))
assert (solution == givensolution)
list_solutions = get_potential_solutions(A, B)
list_solutions = filter_solutions(list_solutions)
print_all(flatten_list(list_solutions))

Answer 2

It's unclear to me why you didn't chose to use a tree. From your example you know:

• A[0] has the children B[0:].
• A[1] has the children B[1:].

• A[2] has the children B[1:].

• B[0] has the children A[2:].

• B[1] has no children.
• B[2] has no children.

From this you should be able to see that you'll just have to walk the tree to get the values.

To get all the values you walk the tree with the roots being all the values in A. And you filter odd results.

class Node:
 def __init__(self, value):
 self.value = value
 self.children = []
 def walk(self, path=None):
 path = (path or ()) + (self.value,)
 yield path
 for child in self.children:
 yield from child.walk(path)
def solution(A, B):
 A = [Node(a) for a in A]
 B = [Node(b) for b in B]
 for parents, children in ((A, B), (B, A)):
 for parent in parents:
 parent.children = [
 child
 for child in children
 if child.value > parent.value
 ]
 for start in A:
 for values in start.walk():
 if len(values) % 2 == 0:
 print(values)

• MrJoe: I actually never considered that as a possibility. But it makes so much sense!
• MrJoe: On second thoughts....A tree as above wouldn't work if the inputs were A = [10,15,20] and B was [1,4,15,20]. The example I gave perhaps was too simple. But it is possible for elements in B to be smaller than those in A at the equivalent position
• Peilonrayz: @EML I have tested the above code. It works with that input. Notice how I didn't discriminate by index in the selection of the children.
• MrJoe: I tried to break down your for parents, children... loop into two separate loops for parent in A: parent.children = [child for child in B if child.value > parent.value] and for parent in B: parent.children = [child for child in B if child.value > parent.value] but this didn't work. Do you know why? Thanks
• Peilonrayz: @EML Second loop, comprehension and outer loop both loop over B.

Answer 3

Just another approach. It is recursive solution, so it can't process big lists. I get "maximum recursion depth exceeded" with more than 1000 items lists. Also, I think it is slow, because it walks through both lists from the beginning every time to greater number search. But it is easy and short, so as an example.

def possible_arrays(lis, num, selector, buf):
 for val in lis[selector]: 
 if val > num:
 if selector:
 print(*buf, val)
 possible_arrays(lis, val, selector ^ 1, buf + [val])

Explanation:

selector ^ 1 - is an exclusive or logical operation. I use it for fast switching selector from 1 to 0 or from 0 to 1. It is needed, because the lis variable is a list comprising two lists: l_a and l_b and I want to select one or another alternately. lis[0] points to l_a, lis[1] points to l_b.

For example: in the first possible_arrays function call the selector equals to 0, so we work with the first list (l_a). When the necessary number is found, we should change the working list to the second one (l_b). We achieve this by doing selector ^ 1 -> 0 ^ 1 -> 1 and passing the 1 to the next possible_arrays call. In the next call, when we should switch back to the first list, we do selector ^ 1 -> 1 ^ 1 -> 0 again. And so on. This way we alternate used lists from one to another as the task was supposing.

Test 1:

l_a = [10, 15, 25]
l_b = [1, 5, 20, 30]
l_main = [l_a, l_b]
possible_arrays(l_main, 0, 0, [])

Output:

10 20
10 20 25 30
10 30
15 20
15 20 25 30
15 30
25 30

Test 2:

l_a = [1, 2, 3]
l_b = [2, 4, 6]
l_main = [l_a, l_b]
possible_arrays(l_main, 0, 0, [])

Output:

1 2
1 2 3 4
1 2 3 6
1 4
1 6
2 4
2 6
3 4
3 6