Styjun

Why do player start with fighting for the corners in go?

How do people drown while wearing a life jacket?

How does shared_ptr<void> know which destructor to use?

What is Albrecht Dürer's Perspective Machine drawing style?

Word for pulling a punch in karate

Is it moral to remove/hide certain parts of a photo, as a photographer?

Why interlaced CRT scanning wasn't done back and forth?

Need help identifying how to open this bolt/screw

Has J.J.Jameson ever found out that Peter Parker is Spider-Man?

What printing process is this?

How to handle many times series?

characteristic of ring

Word to describe someone doing something even though told not to

What is the reason behind water not falling from a bucket at the top of loop?

Subverting the essence of fictional and/or religious entities; is it acceptable?

Where do I keep track of sorcery points on a character sheet?

Skipping same old introductions

What license to choose for my PhD thesis?

Can birds evolve without trees?

Why are sugars in whole fruits not digested the same way sugars in juice are?

Can't understand an ACT practice problem: Triangle appears to be isosceles, why isn't the answer 7.3~ here?

Is law enforcement responsible for damages made by a search warrant?

Detect lightning:recordForm change in mode attribute

Search and replace a substring only if another substring is not present

Remove proper subsets from list of sets

Efficient algorithm for finding all maximal subsetsHow do I check if a list is empty?Finding the index of an item given a list containing it in PythonWhat is the difference between Python's list methods append and extend?How to randomly select an item from a list?How to remove an element from a list by index?How to make a flat list out of list of listsImprove INSERT-per-second performance of SQLite?How to clone or copy a list?How do I list all files of a directory?Replacing a 32-bit loop counter with 64-bit introduces crazy performance deviations

.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty,.everyoneloves__bot-mid-leaderboard:empty margin-bottom:0;

0

I'm trying to remove all the proper subsets from a list of sets. From the top of my head, I was thinking about using 2 for loops to check if an element is a proper subset of all the elements, however, that is too slow.

The code I was thinking about:

Let A be a list of sets

Let B be an empty list

for elm in A:
 for i in range(len(A)):
 if elm.issubset(A[i]) and elm != A[i]:
 B.append(elm)
for junk in B:
 A.remove(junk)

I looked at some answers, and saw this post:
Efficient algorithm for finding all maximal subsets
which works with getting rid of all subsets but I run into a problem when there are 2 sets that are the same, since 2 equal sets are subsets to each other. If 2 sets are the same, then it gets rid of both of them, that's why I'd like to get rid of only proper subsets rather than just all subsets.

python performance set

share|improve this question

asked Mar 27 at 1:08

Kevin LeKevin Le

3188 bronze badges

add a comment | 

0

I'm trying to remove all the proper subsets from a list of sets. From the top of my head, I was thinking about using 2 for loops to check if an element is a proper subset of all the elements, however, that is too slow.

The code I was thinking about:

Let A be a list of sets

Let B be an empty list

for elm in A:
 for i in range(len(A)):
 if elm.issubset(A[i]) and elm != A[i]:
 B.append(elm)
for junk in B:
 A.remove(junk)

I looked at some answers, and saw this post:
Efficient algorithm for finding all maximal subsets
which works with getting rid of all subsets but I run into a problem when there are 2 sets that are the same, since 2 equal sets are subsets to each other. If 2 sets are the same, then it gets rid of both of them, that's why I'd like to get rid of only proper subsets rather than just all subsets.

python performance set

share|improve this question

asked Mar 27 at 1:08

Kevin LeKevin Le

3188 bronze badges

add a comment | 

I'm trying to remove all the proper subsets from a list of sets. From the top of my head, I was thinking about using 2 for loops to check if an element is a proper subset of all the elements, however, that is too slow.

The code I was thinking about:

Let A be a list of sets

Let B be an empty list

for elm in A:
 for i in range(len(A)):
 if elm.issubset(A[i]) and elm != A[i]:
 B.append(elm)
for junk in B:
 A.remove(junk)

I looked at some answers, and saw this post:
Efficient algorithm for finding all maximal subsets
which works with getting rid of all subsets but I run into a problem when there are 2 sets that are the same, since 2 equal sets are subsets to each other. If 2 sets are the same, then it gets rid of both of them, that's why I'd like to get rid of only proper subsets rather than just all subsets.

python performance set

share|improve this question

asked Mar 27 at 1:08

Kevin LeKevin Le

3188 bronze badges

for elm in A:
 for i in range(len(A)):
 if elm.issubset(A[i]) and elm != A[i]:
 B.append(elm)
for junk in B:
 A.remove(junk)

share|improve this question

asked Mar 27 at 1:08

Kevin LeKevin Le

3188 bronze badges

share|improve this question

asked Mar 27 at 1:08

Kevin LeKevin Le

3188 bronze badges

asked Mar 27 at 1:08

Kevin LeKevin Le

3188 bronze badges

asked Mar 27 at 1:08

Kevin LeKevin Le

3188 bronze badges

1 Answer
1

active

oldest

votes

0

Sounds like an assignment for dynamic programming. So I won't present you the final solution in code. Rather, I will give you some hints.

Denote the length of list A as N. Imagine a N by N matrix of 1 and 0, denoted as X. If X(i, j) is 1, it means A[i] is proper subset of A[j], otherwise 0. Your task is to fill up the whole matrix X with minimal work.

There are several kinds of inference you can make on the matrix X:

1. 
   X(i, j) == 1 implies X(j, i) == 0
   


2. 
   len(A[i]) >= len(A[j]) implies X(i, j) == 0
   


3. 
   X(i, j) == 1 and X(j, k) == 1 implies X(i, k) == 1
   

Your task in designing the algorithm is to order the comparisons in a way such that the number of required comparison on average to fill X is minimal, mostly by making use of the rules above as often as possible.

share|improve this answer

answered Mar 27 at 2:26

PM HuiPM Hui

15666 bronze badges

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');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name

Email

Required, but never shown

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f55368352%2fremove-proper-subsets-from-list-of-sets%23new-answer', 'question_page');

);

Post as a guest

Name

Email

Required, but never shown

0

Sounds like an assignment for dynamic programming. So I won't present you the final solution in code. Rather, I will give you some hints.

Denote the length of list A as N. Imagine a N by N matrix of 1 and 0, denoted as X. If X(i, j) is 1, it means A[i] is proper subset of A[j], otherwise 0. Your task is to fill up the whole matrix X with minimal work.

There are several kinds of inference you can make on the matrix X:

1. 
   X(i, j) == 1 implies X(j, i) == 0
   


2. 
   len(A[i]) >= len(A[j]) implies X(i, j) == 0
   


3. 
   X(i, j) == 1 and X(j, k) == 1 implies X(i, k) == 1
   

Your task in designing the algorithm is to order the comparisons in a way such that the number of required comparison on average to fill X is minimal, mostly by making use of the rules above as often as possible.

share|improve this answer

answered Mar 27 at 2:26

PM HuiPM Hui

15666 bronze badges

add a comment | 

0

Sounds like an assignment for dynamic programming. So I won't present you the final solution in code. Rather, I will give you some hints.

Denote the length of list A as N. Imagine a N by N matrix of 1 and 0, denoted as X. If X(i, j) is 1, it means A[i] is proper subset of A[j], otherwise 0. Your task is to fill up the whole matrix X with minimal work.

There are several kinds of inference you can make on the matrix X:

1. 
   X(i, j) == 1 implies X(j, i) == 0
   


2. 
   len(A[i]) >= len(A[j]) implies X(i, j) == 0
   


3. 
   X(i, j) == 1 and X(j, k) == 1 implies X(i, k) == 1
   

Your task in designing the algorithm is to order the comparisons in a way such that the number of required comparison on average to fill X is minimal, mostly by making use of the rules above as often as possible.

share|improve this answer

answered Mar 27 at 2:26

PM HuiPM Hui

15666 bronze badges

add a comment | 

Sounds like an assignment for dynamic programming. So I won't present you the final solution in code. Rather, I will give you some hints.

Denote the length of list A as N. Imagine a N by N matrix of 1 and 0, denoted as X. If X(i, j) is 1, it means A[i] is proper subset of A[j], otherwise 0. Your task is to fill up the whole matrix X with minimal work.

There are several kinds of inference you can make on the matrix X:

1. 
   X(i, j) == 1 implies X(j, i) == 0
   


2. 
   len(A[i]) >= len(A[j]) implies X(i, j) == 0
   


3. 
   X(i, j) == 1 and X(j, k) == 1 implies X(i, k) == 1
   

Your task in designing the algorithm is to order the comparisons in a way such that the number of required comparison on average to fill X is minimal, mostly by making use of the rules above as often as possible.

share|improve this answer

answered Mar 27 at 2:26

PM HuiPM Hui

15666 bronze badges

share|improve this answer

answered Mar 27 at 2:26

PM HuiPM Hui

15666 bronze badges

answered Mar 27 at 2:26

PM HuiPM Hui

15666 bronze badges

answered Mar 27 at 2:26

PM HuiPM Hui

15666 bronze badges