6
\$\begingroup\$

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  
\$\endgroup\$
  • \$\begingroup\$ Have you figure out the selector ^ 1 moment? I have added explanation to the answer. \$\endgroup\$ – MiniMax Jun 3 at 18:03
  • \$\begingroup\$ Yes thanks. I ran a few examples myself and worked it out. THanks for the update \$\endgroup\$ – EML Jun 3 at 18:18
4
\$\begingroup\$

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))
\$\endgroup\$
  • 2
    \$\begingroup\$ Thanks for this detailed feedback! \$\endgroup\$ – EML Jun 2 at 21:08
5
\$\begingroup\$

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)
\$\endgroup\$
  • \$\begingroup\$ I actually never considered that as a possibility. But it makes so much sense! \$\endgroup\$ – EML Jun 2 at 20:23
  • \$\begingroup\$ 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 \$\endgroup\$ – EML Jun 2 at 20:28
  • 1
    \$\begingroup\$ @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. \$\endgroup\$ – Peilonrayz Jun 2 at 20:30
  • \$\begingroup\$ 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 \$\endgroup\$ – EML Jun 2 at 23:13
  • 1
    \$\begingroup\$ @EML Second loop, comprehension and outer loop both loop over B. \$\endgroup\$ – Peilonrayz Jun 2 at 23:17
2
\$\begingroup\$

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
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.