Algorithm to create all possible combinations of unique pairs of Letters in a List

Watch
FROSTYql
Badges: 3
Rep:
? You'll earn badges for being active around the site. Rep gems come when your posts are rated by other community members.
#1
Report Thread starter 1 week ago
#1
What I want to achieve here is a piece of a bigger project: Given a set of 2n Letters (number of letters is even) I’m trying to write an algorithm in c# which will partition this list into all possible pairs size 2. For example:

List a = (A, B, C, D)

Ive been trying to get this to produce the output:

((A, B),(C,D))
((A, C),(B, D))
((A,D),(B, C))

And for An example such as:

List a = (A, B, C, D, E, F)

I’ve been trying to get this to produce:

((A, B),(C,D),(E, F))
((A, B),(C,E),(D, F))
So on….

If you have any ideas at all please could you explain or talk me through your thoughts it would be really appreciated.
Last edited by FROSTYql; 1 week ago
0
reply
gcseeeman
Badges: 9
Rep:
? You'll earn badges for being active around the site. Rep gems come when your posts are rated by other community members.
#2
Report 1 week ago
#2
How familiar are you with recursion? If you can produce all pairs for a list of size 2n, can you use that to help with a list of size 2*(n+1)?
0
reply
FROSTYql
Badges: 3
Rep:
? You'll earn badges for being active around the site. Rep gems come when your posts are rated by other community members.
#3
Report Thread starter 1 week ago
#3
(Original post by gcseeeman)
How familiar are you with recursion? If you can produce all pairs for a list of size 2n, can you use that to help with a list of size 2*(n+1)?
I know of recursion, but to say I'm any good at it is probably not the case - I'll start studying it and see where I can get to, thanks
0
reply
gcseeeman
Badges: 9
Rep:
? You'll earn badges for being active around the site. Rep gems come when your posts are rated by other community members.
#4
Report 1 week ago
#4
(Original post by FROSTYql)
I know of recursion, but to say I'm any good at it is probably not the case - I'll start studying it and see where I can get to, thanks
If you want to look up some similar examples, finding all subsets of a list and finding all permutations of a list are both canonical examples, and will have plenty of explanations online. The former is easier than this problem. I would say the latter is about the same difficulty.

Note the number of pairs grows very fast! (For 2n, it's (2n-1)*(2n-3)*...*3*1. Once you write recursive code to solve this, the reason for that value should be clear ). So, I hope you aren't expecting this to work for a list much larger than about 14 or 16.

Feel free to ask if you get stuck or want more hints. I can't tell if this is an academic question or a personal one. But, I wanted to practice Python so you can find a rough implementation below:

Spoiler:
Show
Code:
def pairs(a): # Input should be a list of even length, e.g. ["A", "B", "C", "D"]
    if len(a) == 2:
        return [[[a[0],a[1]]]]
    ret = []
    for i in range(1,len(a)):
        p1 = [[a[0],a[i]]]
        rem = a[1:i] + a[i+1:]
        res = pairs(rem)
        for ri in res:
            ret.append(p1 + ri)
    return ret
Last edited by gcseeeman; 1 week ago
0
reply
FROSTYql
Badges: 3
Rep:
? You'll earn badges for being active around the site. Rep gems come when your posts are rated by other community members.
#5
Report Thread starter 1 week ago
#5
Thank you SO much. And yeah it shouldn’t be too many, the letters represent odd valency nodes in a graph/network. Thanks for taking the time to even write code to help me understand. I have just one question - what does this line do?

rem = a[1:i] + a[i+1:]

I’m not very familiar with python syntax. I want to say it creates a sub list but I’m not too sure.
0
reply
gcseeeman
Badges: 9
Rep:
? You'll earn badges for being active around the site. Rep gems come when your posts are rated by other community members.
#6
Report 1 week ago
#6
(Original post by FROSTYql)
Thank you SO much. And yeah it shouldn’t be too many, the letters represent odd valency nodes in a graph/network. Thanks for taking the time to even write code to help me understand. I have just one question - what does this line do?

rem = a[1:i] + a[i+1:]

I’m not very familiar with python syntax. I want to say it creates a sub list but I’m not too sure.
Yeah, you're right.
If a = [0,1,2,3,4,5], i = 3, then a[1:i] + a[i+1:] = [1,2] + [4,5] = [1,2,4,5].

The point is we remove the first pair, p1 = [0,3], and then we generate all pairs for the remaining elements [1,2,4,5] recursively and append [0,3] to each of those lists of pairs ("p1 + ri"). Python list syntax is weird, at least to me, and that took several attempts to get right. I expect C# will be more readable but require a lot of mode.
Last edited by gcseeeman; 1 week ago
0
reply
FROSTYql
Badges: 3
Rep:
? You'll earn badges for being active around the site. Rep gems come when your posts are rated by other community members.
#7
Report Thread starter 1 week ago
#7
(Original post by gcseeeman)
Yeah, you're right.
If a = [0,1,2,3,4,5], i = 3, then a[1:i] + a[i+1:] = [1,2] + [4,5] = [1,2,4,5].

The point is we remove the first pair, p1 = [0,3], and then we generate all pairs for the remaining elements [1,2,4,5] recursively and append [0,3] to each of those lists of pairs ("p1 + ri"). Python list syntax is weird, at least to me, and that took several attempts to get right. I expect C# will be more readable but require a lot of mode.
That's genius! Yes I'll Create some functions to do the sub lists. Is it ok if I come back to you to ask anymore questions if there's still gaps in my understanding?
0
reply
FROSTYql
Badges: 3
Rep:
? You'll earn badges for being active around the site. Rep gems come when your posts are rated by other community members.
#8
Report Thread starter 1 week ago
#8
(Original post by gcseeeman)
Yeah, you're right.
If a = [0,1,2,3,4,5], i = 3, then a[1:i] + a[i+1:] = [1,2] + [4,5] = [1,2,4,5].

The point is we remove the first pair, p1 = [0,3], and then we generate all pairs for the remaining elements [1,2,4,5] recursively and append [0,3] to each of those lists of pairs ("p1 + ri"). Python list syntax is weird, at least to me, and that took several attempts to get right. I expect C# will be more readable but require a lot of mode.
I actually managed to do it it took a long time because I had to make functions for splicing and adding and outputting 1D and 2D lists. Thanks so much for the help.
Last edited by FROSTYql; 1 week ago
0
reply
gcseeeman
Badges: 9
Rep:
? You'll earn badges for being active around the site. Rep gems come when your posts are rated by other community members.
#9
Report 1 week ago
#9
(Original post by FROSTYql)
I actually managed to do it it took a long time because I had to make functions for splicing and adding and outputting 1D and 2D lists. Thanks so hmuch for the help. Here's it finished:
Happy to hear that. Now I feel I should have given fewer hints and left more fun for you But, I suppose there are many problems like this out there you can try if you want more practice.

Normally, the problems have no real purpose. So I would be interested if you elaborate on "the letters represent odd valency nodes in a graph/network" and what this is for?

(Also, have you proved the simple formula for the total number of combinations? )
0
reply
FROSTYql
Badges: 3
Rep:
? You'll earn badges for being active around the site. Rep gems come when your posts are rated by other community members.
#10
Report Thread starter 1 week ago
#10
(Original post by gcseeeman)
Normally, the problems have no real purpose. So I would be interested if you elaborate on "the letters represent odd valency nodes in a graph/network" and what this is for?
Yes of course, its only fair. The purpose of this was so I could write code for the "Route Inspection Algorithm" also known as the "The Chinese Postman Algorithm". Part of this algorithm creates a route (from any starting point) along a network that covers all edges only once (and finishes at that same starting point).

But it's only possible if all the Nodes/Vertices of the graph have an even valency. By valency I mean the number of edges coming out of one Vertex. If some of the Vertices have an odd valency, the algorithm adds them all to a list and finds the shortest possible pairing between these vertices. For example AD, BC (routes between vertices) might be a shorter distance to cover than AC, BD. Which is why I had to consider all possible combinations. The need for this pairing is because by connecting the odd valency vertices together, you make them all even, which makes it possible to complete the goal of this part of the algorithm.

Its also worth stating that the number of Odd valency vertices is proven to be an even number which is where the restriction of 2n came from. I'm an AS-Level student and this is a personal project so sorry if this wasn't very well explained, I learned about it very recently in my further maths class. Here's a diagram if it helps
Attached files
Last edited by FROSTYql; 1 week ago
0
reply
FROSTYql
Badges: 3
Rep:
? You'll earn badges for being active around the site. Rep gems come when your posts are rated by other community members.
#11
Report Thread starter 1 week ago
#11
(Original post by gcseeeman)
(Also, have you proved the simple formula for the total number of combinations? )
No but I love proofs, and will look into this next
0
reply
X

Quick Reply

Attached files
Write a reply...
Reply
new posts
Back
to top
Latest
My Feed

See more of what you like on
The Student Room

You can personalise what you see on TSR. Tell us a little about yourself to get started.

Personalise

What is your favourite revision method?

Taking notes manually (53)
22.27%
Note taking apps (6)
2.52%
Flashcards (45)
18.91%
Revision guides (15)
6.3%
Past papers (111)
46.64%
Something else (let us know in the thread) (8)
3.36%

Watched Threads

View All