Deleting similar elements from a nested list

Question

I am creating a nested list using the following code:

from itertools import combinations


def get_nested_list(arr, n, k):
    iterator = 0
    nest = []

    for i in range(1, n):

        for combo in combinations(arr, i):
            odd_num = 0

            for item in combo:
                if item % 2 != 0:
                    odd_num += 1

            if odd_num <= k:
                iterator += 1
                nest.append(combo)

    nest = [list(i) for i in nest]
    return nest


a = [1, 2, 3, 4]
b = len(a)
c = 1

print(get_nested_list(a, b, c))

This is my output:

[[1], [2], [3], [4], [1, 2], [1, 4], [2, 3], [2, 4], [3, 4], [1, 2, 4], [2, 3, 4]]

However, I got elements like [1,2] and [1,4] that have the same x value, [2, 4] and [3, 4] that have the same y value. How can I create a list with completely distinct sub-lists? This is what I'm trying to accomplish:

[[1], [2], [3], [4], [1, 2], [2, 3], [3, 4], [2, 3, 4]]

OK, what have you already tried? What does your code have to do with the problem? What's your criteria? I mean why do you want to keep `[3, 4]` instead of `[2, 4]` and `[2, 3, 4]` instead of `[1, 2, 4]`? — wjandrea, Feb 11 '20 at 06:16
Ohh, wait, you want overlapping chunks, except `[1, 2, 3]`. I've seen another question about that, one min. — wjandrea, Feb 11 '20 at 06:18
I don't necessarily want to solve it by overlapping it. I want to iterate each sub-list inside the list and see if the x or y value of an element is the same as the x or y value of the next element. — Onur-Andros Ozbek, Feb 11 '20 at 06:19
I don't want two elements of the same size to have their x or y values equal to one another. I hope that explains it better. — Onur-Andros Ozbek, Feb 11 '20 at 06:20
Because each sequence can have at most `k` odd numbers. In this run, `k = 1`. — Onur-Andros Ozbek, Feb 11 '20 at 06:56
Because sub-lists cannot be identical. You already have an element `[2, 3, 4]` that has the same z value as `[1, 2, 4]`. — Onur-Andros Ozbek, Feb 11 '20 at 07:02
So this is valid answer as well? `[[1], [2], [3], [4], [1, 2], [2, 3], [3, 4], [1, 2, 4]]` — cosmic_inquiry, Feb 11 '20 at 07:03
Because if you actually run your code, the first one added is [1, 2, 4] and so it stands to reason that [2, 3, 4] shouldn't be added. Posting my answer... — cosmic_inquiry, Feb 11 '20 at 07:05

score 1 · Accepted Answer · answered Feb 11 '20 at 06:47

1

Instead of deleting the similar ones, don't bother generating them in the first place. Really you don't want combos, you want overlapping chunks (except for the ones which contain more than one odd item, which your code already accounts for, and I adapted here).

def overlapping_chunks(size, sequence):
    """Yield overlapping chunks of sequence."""
    for i in range(len(sequence)-size+1):
        yield sequence[i:i+size]

def powerchunk(sequence):
    """Yield all overlapping chunks of sequence, similar to a powerset."""
    for size in range(1, len(sequence)+1):
        yield from overlapping_chunks(size, sequence)

a = [1, 2, 3, 4]
max_odds = 1
result = [
    chunk for chunk in powerchunk(a)
    if sum(item % 2 != 0 for item in chunk) <= max_odds
    ]
print(result)  # -> [[1], [2], [3], [4], [1, 2], [2, 3], [3, 4], [2, 3, 4]]

Related: Splitting a Python list into a list of overlapping chunks

answered Feb 11 '20 at 06:47

wjandrea

28,235
9
60
81

What do `sequence` and `size` represent in relation to my code? – Onur-Andros Ozbek Feb 11 '20 at 06:49
`sequence` is `arr` in your code and `size` is `i` (`for i in range(1, n)`) – wjandrea Feb 11 '20 at 06:50
Are these nested definitions? How are you accessing i outside of `get_nested_list`? – Onur-Andros Ozbek Feb 11 '20 at 06:51
Well the structure's totally different since I didn't use your code as the source. `overlapping_chunks` is a function I already had sitting around and `powerchunk` is based on a [`powerset` function I wrote already](https://stackoverflow.com/a/59217555/4518341). – wjandrea Feb 11 '20 at 06:53
Got it. Thanx m8. I'll accept your answer and already upvoted it. If you think that this was a well asked question, could you upvote me as well? – Onur-Andros Ozbek Feb 11 '20 at 06:53
if `size` is `i`, then how do I make sense of the line `sequence[i:i+size]`? You're just doubling `i` each time then. Are you sure that `size` isn't `n`? – Onur-Andros Ozbek Feb 11 '20 at 07:06
Like I said, it's a different structure. `overlapping_chunks` has the same role as `combinations` in your code, so you don't even have an equivalent of that variable. `i` is the index where the slice starts. – wjandrea Feb 11 '20 at 07:16
I see. Could you demo how I can apply this logic to my code? – Onur-Andros Ozbek Feb 11 '20 at 07:17

score 0 · Answer 2 · answered Feb 11 '20 at 07:07

The selected answer is obviously simpler, but I worked on this so posting my answer anyways. It uses defaultdict and some logic to check if an existing entry at that index and with the same length has been there.

from itertools import combinations
from collections import defaultdict

def get_nested_list(arr, n, k):
    iterator = 0
    nest = []
    d = defaultdict(set)

    for i in range(1, n):

        for combo in combinations(arr, i):
            odd_num = 0

            for item in combo:
                if item % 2 != 0:
                    odd_num += 1

            if odd_num <= k:
                iterator += 1
                skip = False
                len_c = len(combo)
                for j, n in enumerate(combo):
                    if n in d.get((len_c, j), set()):
                        skip = True
                        break
                    d[(len_c, j)].add(n)
                if skip: continue
                nest.append(combo)

    nest = [list(i) for i in nest]
    return nest

a = [1, 2, 3, 4]
b = len(a)
c = 1
res = get_nested_list(a, b, c)
print(res)

assert res == [[1], [2], [3], [4], [1, 2], [2, 3], [3, 4], [1, 2, 4]]

On a different example?? I'm confused by what you mean? It returns: `[[1], [2], [3], [4], [1, 2], [2, 3], [3, 4], [1, 2, 4]]` and that value is assigned to `res` — cosmic_inquiry, Feb 11 '20 at 07:37
Actually, your code is throwing some issues. For `a = [3, 2, 3, 4]` and `k = 1`, the output should be 7 but its giving me 6. For `a = [2, 2, 5, 6, 9, 2, 11, 9, 2, 11, 12]` and `k = 1`, the output should be 18 but its giving 17. — Onur-Andros Ozbek, Feb 11 '20 at 08:06

Deleting similar elements from a nested list

2 Answers2