Combinations and Possibilities

Q&A Non-DQ Courses
#1

Hello. I have a small challenge from a coworker which has puzzled me. Let’s say I have ten letters A-J. I want every possible unique combination where only 3 letters are taken XYZ and none are duplicate.
ABC, ACB. BAC = all the same and should not be included as a unique item. Below is as far as I got. Was not as simple as I thought it would be. I know modules exist which can do this but I’d like to be able to make something like this if possible.

Thank you!

listo = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J']
final_list = []
tempvar = ""
vortex = len(tempvar)

for items in listo:
    if items not in tempvar:
        if len(tempvar) < 3:
            tempvar += items
    final_list.append(tempvar)
print(final_list)
1 Like
#2

So what do you think is the problem with the code currently, and where are you stuck?
Why is vortex defined but not used?

This looks like the kind of problem where the more math properties you can extract from the problem, the less code you need to write.

Since this question asks for distinct sets of 3 letters where permutations of them are considered the same, iterating in one direction only and reducing the number of items checked in each iteration is a common strategy.
My main strategy is to “keep moving forward”, and sub-strategy is to simplify the problem down from 3 letters to 2 letters.

So assuming i only needed to pick 2 letters, and for the convenience of implementing the iteration so it only moves in 1 direction from left to right, i begin by left flushing my choices and picking A,B for the 1st outer iteration. In future outer iterations, i would pick {A,C} {A,D}…{A,I}. Notice that this is kind of like finding all the possible pairs given a list of letters. What this ensures is that the first 2 letters at least are unique, at least for the outer iteration.

Now we need 3 letters, so this is what the inner iteration is for. For the 1st outer iteration of {A,B}, i would add {C}, {D}…{J} to the inner iteration to form {A,B,C}, {A,B,D}, …{A,B,J}. Important to note that the 3rd letter chosen must be to the right of the 2nd letter to prevent counting a 3 letter combination previously accounted for in a previous outer iteration. The previous paragraph describing outer iteration ensures that the 1st 2 letters will never duplicate, and by starting the inner iteration after the 2nd letter (moving right or left for 3rd letter doesn’t matter, for coding/thought clarity, just move right for both outer/inner loops) , it ensures that all 3 letter combinations generated are unique.

After all {A,B,?} are accounted, we move to the 2nd outer iteration, A stays there, B moves to C, inner iteration starts at D to end. So it becomes {A,C}+{D/E/F…J}.Repeat the previous until {A,I} is used. Now all of A has finished, move to {B,C},{B,D},…{B,I}, then move to {C,D}, you get the pattern now.

If you agree with the above argument, how would you implement it in code? You can use nCr calculators to verify the code. To generate listo, you can do easier syntax using list('ABCDE...') to save typing quotes and commas

1 Like
#3

Hi @eugeniosp3,
I liked the puzzle you proposed and I think @hanqi has given a nice explanation and a methodical way to construct a solution. I think I’ve found a way to translate what @hanqi said into a code I would be happy to share it if you want.

#4

Of course. Yes please!

#5

Hi @eugeniosp3 @hanqi,
This the code

listo = list('ABCDEFGHIJ')
final_list = []
L = len(listo) #nbr of elements in the list 
for i in range(0,L):
    for j in range(i+1,L):
        for k in range(j+1,L):
            s = listo[i]+listo[j]+listo[k]
            final_list.append(s)
1 Like
#6

Nice demonstration of using range(n,n) to break loop and appending at innermost nest which prevents 2 letter and 1 letter lists from being appended into final_list

1 Like
#7

I just tried using sample() from random package to avoid many for loops. But I feel “While True” is not a safe programming. Let me know your views

import random

input_str =‘ABCDEFGHIJ’
input_no_sup = “”

Avoid duplicated from input string

for a in input_str:
if a not in input_no_sup:
input_no_sup = input_no_sup+a
print(“Input string = {} and Its Unique format {}”.format(input_str, input_no_sup))

calculating possible unique combination for the input string

combo = sum(range(1,len(input_no_sup)))
print(“Possible Unique combination is {}”.format(combo))
count=0

iterating until we get all unique combination

li =
while True:
temp = random.sample(input_no_sup,2)
x = temp[:]
x.reverse()
if temp not in li and x not in li:
li.append(temp)
count +=1
# print(li, count, combo)
if count >= combo:
break

print(‘Unique combination is {} \n {}’.format(len(li), li))