Return a set of pairs of keys from a dictionary that have a common value

How can I write a function, that would take a dictionary and return me a set that would consist of pairs of keys that have at least one common value?

Example:

I have the following dictionary:

dict = {

'C': {'123'}, 

'A': {'123', '456'}, 

'D': {'123'}, 

'B': {'789', '456'}, 

'E': {'789'}}

MyFunction(dict) should return me:

{("A", "B"), ("A", "C"), ("A", "D"), ("B", "E"), ("C", "D")}

edited Nov 21 '18 at 21:40

jpp

101k2163112

asked Nov 21 '18 at 21:30

Tadej Firšt

155

Side note: never (even as an example) shadow built-ins, e.g. use d or dct or dict_ instead of dict.

– jpp
Nov 21 '18 at 21:49

add a comment |

How can I write a function, that would take a dictionary and return me a set that would consist of pairs of keys that have at least one common value?

Example:

I have the following dictionary:

dict = {

'C': {'123'}, 

'A': {'123', '456'}, 

'D': {'123'}, 

'B': {'789', '456'}, 

'E': {'789'}}

MyFunction(dict) should return me:

{("A", "B"), ("A", "C"), ("A", "D"), ("B", "E"), ("C", "D")}

edited Nov 21 '18 at 21:40

jpp

101k2163112

asked Nov 21 '18 at 21:30

Tadej Firšt

155

Side note: never (even as an example) shadow built-ins, e.g. use d or dct or dict_ instead of dict.

– jpp
Nov 21 '18 at 21:49

add a comment |

How can I write a function, that would take a dictionary and return me a set that would consist of pairs of keys that have at least one common value?

Example:

I have the following dictionary:

dict = {

'C': {'123'}, 

'A': {'123', '456'}, 

'D': {'123'}, 

'B': {'789', '456'}, 

'E': {'789'}}

MyFunction(dict) should return me:

{("A", "B"), ("A", "C"), ("A", "D"), ("B", "E"), ("C", "D")}

edited Nov 21 '18 at 21:40

jpp

101k2163112

asked Nov 21 '18 at 21:30

Tadej Firšt

155

How can I write a function, that would take a dictionary and return me a set that would consist of pairs of keys that have at least one common value?

Example:

I have the following dictionary:

dict = {

'C': {'123'}, 

'A': {'123', '456'}, 

'D': {'123'}, 

'B': {'789', '456'}, 

'E': {'789'}}

MyFunction(dict) should return me:

{("A", "B"), ("A", "C"), ("A", "D"), ("B", "E"), ("C", "D")}

python python-3.x function dictionary set

edited Nov 21 '18 at 21:40

jpp

101k2163112

asked Nov 21 '18 at 21:30

Tadej Firšt

155

edited Nov 21 '18 at 21:40

jpp

101k2163112

asked Nov 21 '18 at 21:30

Tadej Firšt

155

edited Nov 21 '18 at 21:40

jpp

101k2163112

edited Nov 21 '18 at 21:40

jpp

101k2163112

edited Nov 21 '18 at 21:40

jpp

101k2163112

asked Nov 21 '18 at 21:30

Tadej Firšt

155

asked Nov 21 '18 at 21:30

Tadej Firšt

155

asked Nov 21 '18 at 21:30

Tadej Firšt

155

Side note: never (even as an example) shadow built-ins, e.g. use d or dct or dict_ instead of dict.

– jpp
Nov 21 '18 at 21:49

add a comment |

Side note: never (even as an example) shadow built-ins, e.g. use d or dct or dict_ instead of dict.

– jpp
Nov 21 '18 at 21:49

Side note: never (even as an example) shadow built-ins, e.g. use d or dct or dict_ instead of dict.

– jpp
Nov 21 '18 at 21:49

add a comment |

3 Answers
3

active

oldest

votes

A more efficient one-pass solution would be to use a seen dict that keeps track of a list of keys that have "seen" a given value so far:

pairs = set()

seen = {}

for key, values in d.items():

    for value in values:

        if value in seen:

            for seen_key in seen[value]:

                pairs.add(frozenset((key, seen_key)))

        seen.setdefault(value, ).append(key)

pairs would become:

{frozenset({'D', 'A'}), frozenset({'B', 'E'}), frozenset({'B', 'A'}), frozenset({'C', 'D'}), frozenset({'C', 'A'})}

You can then easily transform it to a set of lexicographically sorted tuples if you want:

{tuple(sorted(p)) for p in pairs}

which returns:

{('A', 'C'), ('B', 'E'), ('C', 'D'), ('A', 'D'), ('A', 'B')}

answered Nov 21 '18 at 22:07

blhsing

34k41538

add a comment |

Using itertools.combinations:

from itertools import combinations



d = {

    'C': {'123'}, 

    'A': {'123', '456'}, 

    'D': {'123'}, 

    'B': {'789', '456'}, 

    'E': {'789'}

}



def MyFunction(d):

    out = set()

    for i, j in combinations(d, 2):

        if d[j].intersection(d[i]) and (i, j) not in out and (j, i) not in out:

            out.add((i, j))

    return set(tuple(sorted(i)) for i in out)



print(MyFunction(d))

print(MyFunction(d) == {("A", "B"), ("A", "C"), ("A", "D"), ("B", "E"), ("C", "D")})

Output is:

{('A', 'D'), ('A', 'B'), ('B', 'E'), ('A', 'C'), ('C', 'D')}

True

If you consider ('A', 'C') and ('C', 'A') same, you can replace

return set(tuple(sorted(i)) for i in out)

with just

return out

edited Nov 21 '18 at 23:21

answered Nov 21 '18 at 23:10

slavos1

466

add a comment |

`defaultdict` + `combinations`

For a brute force solution, you can invert your dictionary of sets, then use a set comprehension:

from collections import defaultdict

from itertools import combinations



d = {'C': {'123'}, 'A': {'123', '456'}, 

     'D': {'123'}, 'B': {'789', '456'}, 

     'E': {'789'}}



dd = defaultdict(set)



for k, v in d.items():

    for w in v:

        dd[w].add(k)



res = {frozenset(i) for v in dd.values() if len(v) >= 2 for i in combinations(v, 2)}



print(res)



{frozenset({'A', 'D'}), frozenset({'C', 'D'}),

 frozenset({'B', 'E'}), frozenset({'B', 'A'}),

 frozenset({'C', 'A'})}

As you can see the items in res are frozenset objects, i.e. they aren't depending on sorting within tuples. frozenset is required instead of set since set is not hashable.

answered Nov 21 '18 at 21:37

jpp

101k2163112

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%2f53420730%2freturn-a-set-of-pairs-of-keys-from-a-dictionary-that-have-a-common-value%23new-answer', 'question_page');
}
);

Post as a guest

Name

Required, but never shown

3 Answers
3

active

oldest

votes

3 Answers
3

active

oldest

votes

A more efficient one-pass solution would be to use a seen dict that keeps track of a list of keys that have "seen" a given value so far:

pairs = set()

seen = {}

for key, values in d.items():

    for value in values:

        if value in seen:

            for seen_key in seen[value]:

                pairs.add(frozenset((key, seen_key)))

        seen.setdefault(value, ).append(key)

pairs would become:

{frozenset({'D', 'A'}), frozenset({'B', 'E'}), frozenset({'B', 'A'}), frozenset({'C', 'D'}), frozenset({'C', 'A'})}

You can then easily transform it to a set of lexicographically sorted tuples if you want:

{tuple(sorted(p)) for p in pairs}

which returns:

{('A', 'C'), ('B', 'E'), ('C', 'D'), ('A', 'D'), ('A', 'B')}

answered Nov 21 '18 at 22:07

blhsing

34k41538

add a comment |

A more efficient one-pass solution would be to use a seen dict that keeps track of a list of keys that have "seen" a given value so far:

pairs = set()

seen = {}

for key, values in d.items():

    for value in values:

        if value in seen:

            for seen_key in seen[value]:

                pairs.add(frozenset((key, seen_key)))

        seen.setdefault(value, ).append(key)

pairs would become:

{frozenset({'D', 'A'}), frozenset({'B', 'E'}), frozenset({'B', 'A'}), frozenset({'C', 'D'}), frozenset({'C', 'A'})}

You can then easily transform it to a set of lexicographically sorted tuples if you want:

{tuple(sorted(p)) for p in pairs}

which returns:

{('A', 'C'), ('B', 'E'), ('C', 'D'), ('A', 'D'), ('A', 'B')}

answered Nov 21 '18 at 22:07

blhsing

34k41538

add a comment |

A more efficient one-pass solution would be to use a seen dict that keeps track of a list of keys that have "seen" a given value so far:

pairs = set()

seen = {}

for key, values in d.items():

    for value in values:

        if value in seen:

            for seen_key in seen[value]:

                pairs.add(frozenset((key, seen_key)))

        seen.setdefault(value, ).append(key)

pairs would become:

{frozenset({'D', 'A'}), frozenset({'B', 'E'}), frozenset({'B', 'A'}), frozenset({'C', 'D'}), frozenset({'C', 'A'})}

You can then easily transform it to a set of lexicographically sorted tuples if you want:

{tuple(sorted(p)) for p in pairs}

which returns:

{('A', 'C'), ('B', 'E'), ('C', 'D'), ('A', 'D'), ('A', 'B')}

answered Nov 21 '18 at 22:07

blhsing

34k41538

A more efficient one-pass solution would be to use a seen dict that keeps track of a list of keys that have "seen" a given value so far:

pairs = set()

seen = {}

for key, values in d.items():

    for value in values:

        if value in seen:

            for seen_key in seen[value]:

                pairs.add(frozenset((key, seen_key)))

        seen.setdefault(value, ).append(key)

pairs would become:

{frozenset({'D', 'A'}), frozenset({'B', 'E'}), frozenset({'B', 'A'}), frozenset({'C', 'D'}), frozenset({'C', 'A'})}

You can then easily transform it to a set of lexicographically sorted tuples if you want:

{tuple(sorted(p)) for p in pairs}

which returns:

{('A', 'C'), ('B', 'E'), ('C', 'D'), ('A', 'D'), ('A', 'B')}

answered Nov 21 '18 at 22:07

blhsing

34k41538

answered Nov 21 '18 at 22:07

blhsing

34k41538

answered Nov 21 '18 at 22:07

blhsing

34k41538

answered Nov 21 '18 at 22:07

blhsing

34k41538

add a comment |

Using itertools.combinations:

from itertools import combinations



d = {

    'C': {'123'}, 

    'A': {'123', '456'}, 

    'D': {'123'}, 

    'B': {'789', '456'}, 

    'E': {'789'}

}



def MyFunction(d):

    out = set()

    for i, j in combinations(d, 2):

        if d[j].intersection(d[i]) and (i, j) not in out and (j, i) not in out:

            out.add((i, j))

    return set(tuple(sorted(i)) for i in out)



print(MyFunction(d))

print(MyFunction(d) == {("A", "B"), ("A", "C"), ("A", "D"), ("B", "E"), ("C", "D")})

Output is:

{('A', 'D'), ('A', 'B'), ('B', 'E'), ('A', 'C'), ('C', 'D')}

True

If you consider ('A', 'C') and ('C', 'A') same, you can replace

return set(tuple(sorted(i)) for i in out)

with just

return out

edited Nov 21 '18 at 23:21

answered Nov 21 '18 at 23:10

slavos1

466

add a comment |

Using itertools.combinations:

from itertools import combinations



d = {

    'C': {'123'}, 

    'A': {'123', '456'}, 

    'D': {'123'}, 

    'B': {'789', '456'}, 

    'E': {'789'}

}



def MyFunction(d):

    out = set()

    for i, j in combinations(d, 2):

        if d[j].intersection(d[i]) and (i, j) not in out and (j, i) not in out:

            out.add((i, j))

    return set(tuple(sorted(i)) for i in out)



print(MyFunction(d))

print(MyFunction(d) == {("A", "B"), ("A", "C"), ("A", "D"), ("B", "E"), ("C", "D")})

Output is:

{('A', 'D'), ('A', 'B'), ('B', 'E'), ('A', 'C'), ('C', 'D')}

True

If you consider ('A', 'C') and ('C', 'A') same, you can replace

return set(tuple(sorted(i)) for i in out)

with just

return out

edited Nov 21 '18 at 23:21

answered Nov 21 '18 at 23:10

slavos1

466

add a comment |

Using itertools.combinations:

from itertools import combinations



d = {

    'C': {'123'}, 

    'A': {'123', '456'}, 

    'D': {'123'}, 

    'B': {'789', '456'}, 

    'E': {'789'}

}



def MyFunction(d):

    out = set()

    for i, j in combinations(d, 2):

        if d[j].intersection(d[i]) and (i, j) not in out and (j, i) not in out:

            out.add((i, j))

    return set(tuple(sorted(i)) for i in out)



print(MyFunction(d))

print(MyFunction(d) == {("A", "B"), ("A", "C"), ("A", "D"), ("B", "E"), ("C", "D")})

Output is:

{('A', 'D'), ('A', 'B'), ('B', 'E'), ('A', 'C'), ('C', 'D')}

True

If you consider ('A', 'C') and ('C', 'A') same, you can replace

return set(tuple(sorted(i)) for i in out)

with just

return out

edited Nov 21 '18 at 23:21

answered Nov 21 '18 at 23:10

slavos1

466

Using itertools.combinations:

from itertools import combinations



d = {

    'C': {'123'}, 

    'A': {'123', '456'}, 

    'D': {'123'}, 

    'B': {'789', '456'}, 

    'E': {'789'}

}



def MyFunction(d):

    out = set()

    for i, j in combinations(d, 2):

        if d[j].intersection(d[i]) and (i, j) not in out and (j, i) not in out:

            out.add((i, j))

    return set(tuple(sorted(i)) for i in out)



print(MyFunction(d))

print(MyFunction(d) == {("A", "B"), ("A", "C"), ("A", "D"), ("B", "E"), ("C", "D")})

Output is:

{('A', 'D'), ('A', 'B'), ('B', 'E'), ('A', 'C'), ('C', 'D')}

True

If you consider ('A', 'C') and ('C', 'A') same, you can replace

return set(tuple(sorted(i)) for i in out)

with just

return out

edited Nov 21 '18 at 23:21

answered Nov 21 '18 at 23:10

slavos1

466

edited Nov 21 '18 at 23:21

answered Nov 21 '18 at 23:10

slavos1

466

answered Nov 21 '18 at 23:10

slavos1

466

answered Nov 21 '18 at 23:10

slavos1

466

add a comment |

`defaultdict` + `combinations`

For a brute force solution, you can invert your dictionary of sets, then use a set comprehension:

from collections import defaultdict

from itertools import combinations



d = {'C': {'123'}, 'A': {'123', '456'}, 

     'D': {'123'}, 'B': {'789', '456'}, 

     'E': {'789'}}



dd = defaultdict(set)



for k, v in d.items():

    for w in v:

        dd[w].add(k)



res = {frozenset(i) for v in dd.values() if len(v) >= 2 for i in combinations(v, 2)}



print(res)



{frozenset({'A', 'D'}), frozenset({'C', 'D'}),

 frozenset({'B', 'E'}), frozenset({'B', 'A'}),

 frozenset({'C', 'A'})}

As you can see the items in res are frozenset objects, i.e. they aren't depending on sorting within tuples. frozenset is required instead of set since set is not hashable.

answered Nov 21 '18 at 21:37

jpp

101k2163112

add a comment |

`defaultdict` + `combinations`

For a brute force solution, you can invert your dictionary of sets, then use a set comprehension:

from collections import defaultdict

from itertools import combinations



d = {'C': {'123'}, 'A': {'123', '456'}, 

     'D': {'123'}, 'B': {'789', '456'}, 

     'E': {'789'}}



dd = defaultdict(set)



for k, v in d.items():

    for w in v:

        dd[w].add(k)



res = {frozenset(i) for v in dd.values() if len(v) >= 2 for i in combinations(v, 2)}



print(res)



{frozenset({'A', 'D'}), frozenset({'C', 'D'}),

 frozenset({'B', 'E'}), frozenset({'B', 'A'}),

 frozenset({'C', 'A'})}

As you can see the items in res are frozenset objects, i.e. they aren't depending on sorting within tuples. frozenset is required instead of set since set is not hashable.

answered Nov 21 '18 at 21:37

jpp

101k2163112

add a comment |

`defaultdict` + `combinations`

For a brute force solution, you can invert your dictionary of sets, then use a set comprehension:

from collections import defaultdict

from itertools import combinations



d = {'C': {'123'}, 'A': {'123', '456'}, 

     'D': {'123'}, 'B': {'789', '456'}, 

     'E': {'789'}}



dd = defaultdict(set)



for k, v in d.items():

    for w in v:

        dd[w].add(k)



res = {frozenset(i) for v in dd.values() if len(v) >= 2 for i in combinations(v, 2)}



print(res)



{frozenset({'A', 'D'}), frozenset({'C', 'D'}),

 frozenset({'B', 'E'}), frozenset({'B', 'A'}),

 frozenset({'C', 'A'})}

As you can see the items in res are frozenset objects, i.e. they aren't depending on sorting within tuples. frozenset is required instead of set since set is not hashable.

answered Nov 21 '18 at 21:37

jpp

101k2163112

`defaultdict` + `combinations`

For a brute force solution, you can invert your dictionary of sets, then use a set comprehension:

from collections import defaultdict

from itertools import combinations



d = {'C': {'123'}, 'A': {'123', '456'}, 

     'D': {'123'}, 'B': {'789', '456'}, 

     'E': {'789'}}



dd = defaultdict(set)



for k, v in d.items():

    for w in v:

        dd[w].add(k)



res = {frozenset(i) for v in dd.values() if len(v) >= 2 for i in combinations(v, 2)}



print(res)



{frozenset({'A', 'D'}), frozenset({'C', 'D'}),

 frozenset({'B', 'E'}), frozenset({'B', 'A'}),

 frozenset({'C', 'A'})}

As you can see the items in res are frozenset objects, i.e. they aren't depending on sorting within tuples. frozenset is required instead of set since set is not hashable.

answered Nov 21 '18 at 21:37

jpp

101k2163112

answered Nov 21 '18 at 21:37

jpp

101k2163112

answered Nov 21 '18 at 21:37

jpp

101k2163112

answered Nov 21 '18 at 21:37

jpp

101k2163112

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

Search This Blog

Ufyukyu