Reducing time complexity in comparing contiguous subarrays?

So say I have a list sequences such as this.

I want to remove all sequences where its total sum = N and/or it has a contiguous subarray with sum = N.

For example, if N = 4, then (1,1,2) is not valid since its total is 4. (1,1,3) is also not valid since the (1,3) is also 4. (1,3,1) is also not valid for the same reason.

lst = [ 

    (1,1,1), (1,1,2), (1,1,3), 

    (1,2,1), (1,2,2), (1,2,3), 

    (1,3,1), (1,3,2), (1,3,3), 

    (2,1,1), (2,1,2), (2,1,3), 

    (2,2,1), (2,2,2), (2,2,3), 

    (2,3,1), (2,3,2), (2,3,3), 

    (3,1,1), (3,1,2), (3,1,3), 

    (3,2,1), (3,2,2), (3,2,3), 

    (3,3,1), (3,3,2), (3,3,3) 

]

E.g.

Input: 4 3

Output: 2 1 2

So what I have right now is

lst = [t for t in list(product(range(1,n),repeat=n-1)) if not any((sum(t[l:h+1]) % n == 0) for l, h in combinations(range(len(t)), 2))]

Currently it is in O(n²) if I'm not mistaken. What would be a better way to do this?

asked Nov 19 '18 at 23:59

Thegreatfoo

385

add a comment |

So say I have a list sequences such as this.

I want to remove all sequences where its total sum = N and/or it has a contiguous subarray with sum = N.

For example, if N = 4, then (1,1,2) is not valid since its total is 4. (1,1,3) is also not valid since the (1,3) is also 4. (1,3,1) is also not valid for the same reason.

lst = [ 

    (1,1,1), (1,1,2), (1,1,3), 

    (1,2,1), (1,2,2), (1,2,3), 

    (1,3,1), (1,3,2), (1,3,3), 

    (2,1,1), (2,1,2), (2,1,3), 

    (2,2,1), (2,2,2), (2,2,3), 

    (2,3,1), (2,3,2), (2,3,3), 

    (3,1,1), (3,1,2), (3,1,3), 

    (3,2,1), (3,2,2), (3,2,3), 

    (3,3,1), (3,3,2), (3,3,3) 

]

E.g.

Input: 4 3

Output: 2 1 2

So what I have right now is

lst = [t for t in list(product(range(1,n),repeat=n-1)) if not any((sum(t[l:h+1]) % n == 0) for l, h in combinations(range(len(t)), 2))]

Currently it is in O(n²) if I'm not mistaken. What would be a better way to do this?

asked Nov 19 '18 at 23:59

Thegreatfoo

385

add a comment |

So say I have a list sequences such as this.

I want to remove all sequences where its total sum = N and/or it has a contiguous subarray with sum = N.

For example, if N = 4, then (1,1,2) is not valid since its total is 4. (1,1,3) is also not valid since the (1,3) is also 4. (1,3,1) is also not valid for the same reason.

lst = [ 

    (1,1,1), (1,1,2), (1,1,3), 

    (1,2,1), (1,2,2), (1,2,3), 

    (1,3,1), (1,3,2), (1,3,3), 

    (2,1,1), (2,1,2), (2,1,3), 

    (2,2,1), (2,2,2), (2,2,3), 

    (2,3,1), (2,3,2), (2,3,3), 

    (3,1,1), (3,1,2), (3,1,3), 

    (3,2,1), (3,2,2), (3,2,3), 

    (3,3,1), (3,3,2), (3,3,3) 

]

E.g.

Input: 4 3

Output: 2 1 2

So what I have right now is

lst = [t for t in list(product(range(1,n),repeat=n-1)) if not any((sum(t[l:h+1]) % n == 0) for l, h in combinations(range(len(t)), 2))]

Currently it is in O(n²) if I'm not mistaken. What would be a better way to do this?

asked Nov 19 '18 at 23:59

Thegreatfoo

385

So say I have a list sequences such as this.

I want to remove all sequences where its total sum = N and/or it has a contiguous subarray with sum = N.

For example, if N = 4, then (1,1,2) is not valid since its total is 4. (1,1,3) is also not valid since the (1,3) is also 4. (1,3,1) is also not valid for the same reason.

lst = [ 

    (1,1,1), (1,1,2), (1,1,3), 

    (1,2,1), (1,2,2), (1,2,3), 

    (1,3,1), (1,3,2), (1,3,3), 

    (2,1,1), (2,1,2), (2,1,3), 

    (2,2,1), (2,2,2), (2,2,3), 

    (2,3,1), (2,3,2), (2,3,3), 

    (3,1,1), (3,1,2), (3,1,3), 

    (3,2,1), (3,2,2), (3,2,3), 

    (3,3,1), (3,3,2), (3,3,3) 

]

E.g.

Input: 4 3

Output: 2 1 2

So what I have right now is

lst = [t for t in list(product(range(1,n),repeat=n-1)) if not any((sum(t[l:h+1]) % n == 0) for l, h in combinations(range(len(t)), 2))]

Currently it is in O(n²) if I'm not mistaken. What would be a better way to do this?

python-3.x

asked Nov 19 '18 at 23:59

Thegreatfoo

385

asked Nov 19 '18 at 23:59

Thegreatfoo

385

asked Nov 19 '18 at 23:59

Thegreatfoo

385

asked Nov 19 '18 at 23:59

Thegreatfoo

385

asked Nov 19 '18 at 23:59

Thegreatfoo

385

add a comment |

1 Answer
1

active

oldest

votes

If you can use numpy, you can concatenate the total sum of each tuple with the contiguous value sums, then check if any of your resultign elements are equal to 4:

arr = np.array(lst)

arr[~(np.concatenate((np.sum(arr,axis=1).reshape(-1,1),

                      (arr[:,:-1]+ arr[:,1:])),axis=1) == 4).any(1)]

# or:

arr[(np.concatenate((np.sum(arr,axis=1).reshape(-1,1),

                      (arr[:,:-1]+ arr[:,1:])),axis=1) != 4).all(1)]

Returning:

array([[1, 1, 1],

       [1, 2, 3],

       [2, 1, 2],

       [2, 3, 2],

       [2, 3, 3],

       [3, 2, 1],

       [3, 2, 3],

       [3, 3, 2],

       [3, 3, 3]])

answered Nov 20 '18 at 0:08

sacuL

30.1k41940

add a comment |

Your Answer

StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");

StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "1"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});

function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});

}
});

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});

Post as a guest

Name

Required, but never shown

StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53384351%2freducing-time-complexity-in-comparing-contiguous-subarrays%23new-answer', 'question_page');
}
);

Post as a guest

Name

Required, but never shown

1 Answer
1

active

oldest

votes

1 Answer
1

active

oldest

votes

If you can use numpy, you can concatenate the total sum of each tuple with the contiguous value sums, then check if any of your resultign elements are equal to 4:

arr = np.array(lst)

arr[~(np.concatenate((np.sum(arr,axis=1).reshape(-1,1),

                      (arr[:,:-1]+ arr[:,1:])),axis=1) == 4).any(1)]

# or:

arr[(np.concatenate((np.sum(arr,axis=1).reshape(-1,1),

                      (arr[:,:-1]+ arr[:,1:])),axis=1) != 4).all(1)]

Returning:

array([[1, 1, 1],

       [1, 2, 3],

       [2, 1, 2],

       [2, 3, 2],

       [2, 3, 3],

       [3, 2, 1],

       [3, 2, 3],

       [3, 3, 2],

       [3, 3, 3]])

answered Nov 20 '18 at 0:08

sacuL

30.1k41940

add a comment |

If you can use numpy, you can concatenate the total sum of each tuple with the contiguous value sums, then check if any of your resultign elements are equal to 4:

arr = np.array(lst)

arr[~(np.concatenate((np.sum(arr,axis=1).reshape(-1,1),

                      (arr[:,:-1]+ arr[:,1:])),axis=1) == 4).any(1)]

# or:

arr[(np.concatenate((np.sum(arr,axis=1).reshape(-1,1),

                      (arr[:,:-1]+ arr[:,1:])),axis=1) != 4).all(1)]

Returning:

array([[1, 1, 1],

       [1, 2, 3],

       [2, 1, 2],

       [2, 3, 2],

       [2, 3, 3],

       [3, 2, 1],

       [3, 2, 3],

       [3, 3, 2],

       [3, 3, 3]])

answered Nov 20 '18 at 0:08

sacuL

30.1k41940

add a comment |

If you can use numpy, you can concatenate the total sum of each tuple with the contiguous value sums, then check if any of your resultign elements are equal to 4:

arr = np.array(lst)

arr[~(np.concatenate((np.sum(arr,axis=1).reshape(-1,1),

                      (arr[:,:-1]+ arr[:,1:])),axis=1) == 4).any(1)]

# or:

arr[(np.concatenate((np.sum(arr,axis=1).reshape(-1,1),

                      (arr[:,:-1]+ arr[:,1:])),axis=1) != 4).all(1)]

Returning:

array([[1, 1, 1],

       [1, 2, 3],

       [2, 1, 2],

       [2, 3, 2],

       [2, 3, 3],

       [3, 2, 1],

       [3, 2, 3],

       [3, 3, 2],

       [3, 3, 3]])

answered Nov 20 '18 at 0:08

sacuL

30.1k41940

If you can use numpy, you can concatenate the total sum of each tuple with the contiguous value sums, then check if any of your resultign elements are equal to 4:

arr = np.array(lst)

arr[~(np.concatenate((np.sum(arr,axis=1).reshape(-1,1),

                      (arr[:,:-1]+ arr[:,1:])),axis=1) == 4).any(1)]

# or:

arr[(np.concatenate((np.sum(arr,axis=1).reshape(-1,1),

                      (arr[:,:-1]+ arr[:,1:])),axis=1) != 4).all(1)]

Returning:

array([[1, 1, 1],

       [1, 2, 3],

       [2, 1, 2],

       [2, 3, 2],

       [2, 3, 3],

       [3, 2, 1],

       [3, 2, 3],

       [3, 3, 2],

       [3, 3, 3]])

answered Nov 20 '18 at 0:08

sacuL

30.1k41940

answered Nov 20 '18 at 0:08

sacuL

30.1k41940

answered Nov 20 '18 at 0:08

sacuL

30.1k41940

answered Nov 20 '18 at 0:08

sacuL

30.1k41940

add a comment |

draft saved

draft discarded

Thanks for contributing an answer to Stack Overflow!

Please be sure to answer the question. Provide details and share your research!

But avoid …

Asking for help, clarification, or responding to other answers.

Making statements based on opinion; back them up with references or personal experience.

To learn more, see our tips on writing great answers.

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});

Post as a guest

Name

Required, but never shown

Post as a guest

Name

Required, but never shown

Sign up or log in

StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});

Post as a guest

Name

Required, but never shown

Sign up or log in

StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});

Post as a guest

Name

Required, but never shown

Sign up or log in

StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});

Post as a guest

Name

Required, but never shown

Name

Required, but never shown

Name

Required, but never shown

This page is only for reference, If you need detailed information, please check here

搜尋此網誌

Cfrgtkky