[Tutor] problem solving with lists
Dennis Lee Bieber
wlfraed at ix.netcom.com
Wed Mar 9 19:42:09 EST 2022
On Wed, 9 Mar 2022 20:39:56 +0100, <marcus.luetolf at bluewin.ch> declaimed
the following:
>Hello Experts,
>many thanks for your offer. My problem to solve:
>
>for a sublist of length 3 and a list of 9 letters (all_letters =
>list('abcdefghi'))
>create 4 lists ( = (len(all_letters)- 1)/2), each containing 3 sublists
>(9/3) for a total of 12 sublists.
"create 4 lists" is noise... Just create the one list of 12 triplets --
you can THEN split that into your 4x3 layout. That presumes there ARE 12
passing triplets.
>
>Append all 9 letters to each list, 3 letters to each sublist 4 times.
>
>Apply a constraint that in all 12 sublists a pairing of 2 letters can occur
>only once.
>P.e. if the first sublist of the first list = ['a', 'b', 'c'] the
>combination of 'a','b' or 'a', 'c', or 'b','c'
>cannot occur in a sublist in the subsequent lists any more.
>
So far, the above description is essentially the same as the original
post in this thread, except replacing 4-character with 3 and 16-character
with 9 -- except you've now described a constraint that /any/ pair of
letters can not appear a second time, not just adjacent pairs. That means
working with sets and set intersection is viable to filter rejects.
>A solution exists only for a specific lenght of sublists and number of
>letters:
>(number of letters -1)%(length of sublist -1) == 0
>
>In the first part of my algorithm I created sublists of all possible letter
>combInations:
>
>>all_letters = list('abcdefghi')
Just leave this as all string... You can index a string just like a
list.
>
>>l1 = []
>>l2 = []
>>l3 = []
>>l4 = []
>
>>chars = []
>>for index, letter in enumerate(all_letters):
>> copy_all_letters = all_letters[:]
>> del(copy_all_letters[index])
>> lst = copy_all_letters
Why copy "all_letters" only to then remove one based upon index... And
then you attach second name to that copy.
>>> all_letters = "abcdefghi"
>>> ltr = "a"
>>> copy_less = "".join(all_letters.split(ltr))
>>> copy_less
'bcdefghi'
>> l1.append(lst[0])
>> l1.append(lst[1])
>> l1.append(letter)
>> l1.sort()
Again, this brute-force approach is not scalable -- all four
combinations for a given "ltr" can be done
>>> triples = []
>>> for x in range(0, len(copy_less), 2):
... triples.append("".join(sorted([ltr, copy_less[x],
copy_less[x+1]])))
...
>>> triples
['abc', 'ade', 'afg', 'ahi']
>>>
And just if you don't believe the .split(ltr) works...
>>> ltr = "c"
>>> copy_less = "".join(all_letters.split(ltr))
>>> copy_less
'abdefghi'
>>> triples = []
>>> for x in range(0, len(copy_less), 2):
... triples.append("".join(sorted([ltr, copy_less[x],
copy_less[x+1]])))
...
>>> triples
['abc', 'cde', 'cfg', 'chi']
>>>
I don't recommend that approach, BTW -- just showing it in-line with
your brute-force scheme.
>>all_chars = []
>>for i in chars:
>> if i not in all_chars:
>> all_chars.append(i)
>>print('all_chars: ', all_chars, len(all_chars))
>
>In a second step I should create sub_sub_lists containing all possble pairs
>of letters (['a', 'b'], ['a', 'c'] ..... ['i', 'h'] ,
>a total of len(all_letters) -1 * len(all_letters) = 72 and eliminating
>sub_sub_lists with equal pairs when 'a', 'b' = 'b', 'a'.
>
And here is the main problem with your attempt -- in my view. If you
create ALL possible triples first, and THEN try to eliminate those that
share 2 characters, you will eliminate everything! since in any collection
of all possible triples, all pairs will occur multiple times.
Here are all 84 possible triples, generated in TWO lines of code!
>>> import itertools
>>> triples = ["".join(combo) for combo in itertools.combinations("abcdefghi", 3)]
>>> triples
['abc', 'abd', 'abe', 'abf', 'abg', 'abh', 'abi', 'acd', 'ace', 'acf',
'acg', 'ach', 'aci', 'ade', 'adf', 'adg', 'adh', 'adi', 'aef', 'aeg',
'aeh', 'aei', 'afg', 'afh', 'afi', 'agh', 'agi', 'ahi', 'bcd', 'bce',
'bcf', 'bcg', 'bch', 'bci', 'bde', 'bdf', 'bdg', 'bdh', 'bdi', 'bef',
'beg', 'beh', 'bei', 'bfg', 'bfh', 'bfi', 'bgh', 'bgi', 'bhi', 'cde',
'cdf', 'cdg', 'cdh', 'cdi', 'cef', 'ceg', 'ceh', 'cei', 'cfg', 'cfh',
'cfi', 'cgh', 'cgi', 'chi', 'def', 'deg', 'deh', 'dei', 'dfg', 'dfh',
'dfi', 'dgh', 'dgi', 'dhi', 'efg', 'efh', 'efi', 'egh', 'egi', 'ehi',
'fgh', 'fgi', 'fhi', 'ghi']
>>>
You need to generate one triple first, and just accept that this triple
will be unique (there are no others to compare against). Then generate a
second triple and test it against the first triple -- if it shares two
letters, then you reject the second triple and generate another. Repeat
until you have a triple that passes the criteria. You then continue
generating triples and testing against the accepted ones...
Consider this, which is your testing against everything logic... And is
based upon the idea that the letter pairs do not have to adjacent.
>>> for trip1 in triples:
... ctriples = triples[:]
... ctriples.remove(trip1)
... for trip2 in ctriples:
... if len(set(trip1) & set(trip2)) >= 2:
... print("%s REJECTED shares with %s" % (trip1, trip2))
... break
... else:
... print("%s ACCEPTED not shared" % trip1)
...
abc REJECTED shares with abd
abd REJECTED shares with abc
abe REJECTED shares with abc
abf REJECTED shares with abc
abg REJECTED shares with abc
abh REJECTED shares with abc
abi REJECTED shares with abc
acd REJECTED shares with abc
ace REJECTED shares with abc
acf REJECTED shares with abc
acg REJECTED shares with abc
ach REJECTED shares with abc
aci REJECTED shares with abc
ade REJECTED shares with abd
adf REJECTED shares with abd
adg REJECTED shares with abd
adh REJECTED shares with abd
adi REJECTED shares with abd
aef REJECTED shares with abe
aeg REJECTED shares with abe
aeh REJECTED shares with abe
aei REJECTED shares with abe
afg REJECTED shares with abf
afh REJECTED shares with abf
afi REJECTED shares with abf
agh REJECTED shares with abg
agi REJECTED shares with abg
ahi REJECTED shares with abh
bcd REJECTED shares with abc
bce REJECTED shares with abc
bcf REJECTED shares with abc
bcg REJECTED shares with abc
bch REJECTED shares with abc
bci REJECTED shares with abc
bde REJECTED shares with abd
bdf REJECTED shares with abd
bdg REJECTED shares with abd
bdh REJECTED shares with abd
bdi REJECTED shares with abd
bef REJECTED shares with abe
beg REJECTED shares with abe
beh REJECTED shares with abe
bei REJECTED shares with abe
bfg REJECTED shares with abf
bfh REJECTED shares with abf
bfi REJECTED shares with abf
bgh REJECTED shares with abg
bgi REJECTED shares with abg
bhi REJECTED shares with abh
cde REJECTED shares with acd
cdf REJECTED shares with acd
cdg REJECTED shares with acd
cdh REJECTED shares with acd
cdi REJECTED shares with acd
cef REJECTED shares with ace
ceg REJECTED shares with ace
ceh REJECTED shares with ace
cei REJECTED shares with ace
cfg REJECTED shares with acf
cfh REJECTED shares with acf
cfi REJECTED shares with acf
cgh REJECTED shares with acg
cgi REJECTED shares with acg
chi REJECTED shares with ach
def REJECTED shares with ade
deg REJECTED shares with ade
deh REJECTED shares with ade
dei REJECTED shares with ade
dfg REJECTED shares with adf
dfh REJECTED shares with adf
dfi REJECTED shares with adf
dgh REJECTED shares with adg
dgi REJECTED shares with adg
dhi REJECTED shares with adh
efg REJECTED shares with aef
efh REJECTED shares with aef
efi REJECTED shares with aef
egh REJECTED shares with aeg
egi REJECTED shares with aeg
ehi REJECTED shares with aeh
fgh REJECTED shares with afg
fgi REJECTED shares with afg
fhi REJECTED shares with afh
ghi REJECTED shares with agh
>>>
>In a third step append to a final list only sublists not already containing
>one ot the sub_sub_lists
>
This is, as I describe above, not a third step because the "final list"
is what you have to compare against, NOT the complete set of combinations.
(that [above] is NOT optimized -- it would be simpler to have created the
initial "triples" as set() objects, and only convert to strings for final
output).
>It is this third step I am unable to code efficiently, avoiding to hardcode
>it.
>
You've already hard-coded too much...
>>> accepted = []
>>> for trip1 in triples:
<NOT SHOWN AS IT GIVES AWAY TOO MUCH>
<still assumes letter pairs do not have to be adjacent>
abc ACCEPTED not shared with []
abd REJECTED shares with abc
abe REJECTED shares with abc
abf REJECTED shares with abc
abg REJECTED shares with abc
abh REJECTED shares with abc
abi REJECTED shares with abc
acd REJECTED shares with abc
ace REJECTED shares with abc
acf REJECTED shares with abc
acg REJECTED shares with abc
ach REJECTED shares with abc
aci REJECTED shares with abc
ade ACCEPTED not shared with ['abc']
adf REJECTED shares with ade
adg REJECTED shares with ade
adh REJECTED shares with ade
adi REJECTED shares with ade
aef REJECTED shares with ade
aeg REJECTED shares with ade
aeh REJECTED shares with ade
aei REJECTED shares with ade
afg ACCEPTED not shared with ['abc', 'ade']
afh REJECTED shares with afg
afi REJECTED shares with afg
agh REJECTED shares with afg
agi REJECTED shares with afg
ahi ACCEPTED not shared with ['abc', 'ade', 'afg']
bcd REJECTED shares with abc
bce REJECTED shares with abc
bcf REJECTED shares with abc
bcg REJECTED shares with abc
bch REJECTED shares with abc
bci REJECTED shares with abc
bde REJECTED shares with ade
bdf ACCEPTED not shared with ['abc', 'ade', 'afg', 'ahi']
bdg REJECTED shares with bdf
bdh REJECTED shares with bdf
bdi REJECTED shares with bdf
bef REJECTED shares with bdf
beg ACCEPTED not shared with ['abc', 'ade', 'afg', 'ahi', 'bdf']
beh REJECTED shares with beg
bei REJECTED shares with beg
bfg REJECTED shares with afg
bfh REJECTED shares with bdf
bfi REJECTED shares with bdf
bgh REJECTED shares with beg
bgi REJECTED shares with beg
bhi REJECTED shares with ahi
cde REJECTED shares with ade
cdf REJECTED shares with bdf
cdg ACCEPTED not shared with ['abc', 'ade', 'afg', 'ahi', 'bdf', 'beg']
cdh REJECTED shares with cdg
cdi REJECTED shares with cdg
cef ACCEPTED not shared with ['abc', 'ade', 'afg', 'ahi', 'bdf', 'beg',
'cdg']
ceg REJECTED shares with beg
ceh REJECTED shares with cef
cei REJECTED shares with cef
cfg REJECTED shares with afg
cfh REJECTED shares with cef
cfi REJECTED shares with cef
cgh REJECTED shares with cdg
cgi REJECTED shares with cdg
chi REJECTED shares with ahi
def REJECTED shares with ade
deg REJECTED shares with ade
deh REJECTED shares with ade
dei REJECTED shares with ade
dfg REJECTED shares with afg
dfh REJECTED shares with bdf
dfi REJECTED shares with bdf
dgh REJECTED shares with cdg
dgi REJECTED shares with cdg
dhi REJECTED shares with ahi
efg REJECTED shares with afg
efh REJECTED shares with cef
efi REJECTED shares with cef
egh REJECTED shares with beg
egi REJECTED shares with beg
ehi REJECTED shares with ahi
fgh REJECTED shares with afg
fgi REJECTED shares with afg
fhi REJECTED shares with ahi
ghi REJECTED shares with ahi
>>>
>>> accepted
['abc', 'ade', 'afg', 'ahi', 'bdf', 'beg', 'cdg', 'cef']
>>>
NOTE that only 8 triples passed... NOT 12
Changing the code to reject only if the letter pairs are adjacent
produces
abc ACCEPTED not shared with []
abd REJECTED shares with abc
abe REJECTED shares with abc
abf REJECTED shares with abc
abg REJECTED shares with abc
abh REJECTED shares with abc
abi REJECTED shares with abc
acd ACCEPTED not shared with ['abc']
ace REJECTED shares with acd
acf REJECTED shares with acd
acg REJECTED shares with acd
ach REJECTED shares with acd
aci REJECTED shares with acd
ade ACCEPTED not shared with ['abc', 'acd']
adf REJECTED shares with ade
adg REJECTED shares with ade
adh REJECTED shares with ade
adi REJECTED shares with ade
aef ACCEPTED not shared with ['abc', 'acd', 'ade']
aeg REJECTED shares with aef
aeh REJECTED shares with aef
aei REJECTED shares with aef
afg ACCEPTED not shared with ['abc', 'acd', 'ade', 'aef']
afh REJECTED shares with afg
afi REJECTED shares with afg
agh ACCEPTED not shared with ['abc', 'acd', 'ade', 'aef', 'afg']
agi REJECTED shares with agh
ahi ACCEPTED not shared with ['abc', 'acd', 'ade', 'aef', 'afg', 'agh']
bcd REJECTED shares with abc
bce REJECTED shares with abc
bcf REJECTED shares with abc
bcg REJECTED shares with abc
bch REJECTED shares with abc
bci REJECTED shares with abc
bde REJECTED shares with ade
bdf ACCEPTED not shared with ['abc', 'acd', 'ade', 'aef', 'afg', 'agh',
'ahi']
bdg REJECTED shares with bdf
bdh REJECTED shares with bdf
bdi REJECTED shares with bdf
bef REJECTED shares with aef
beg ACCEPTED not shared with ['abc', 'acd', 'ade', 'aef', 'afg', 'agh',
'ahi', 'bdf']
beh REJECTED shares with beg
bei REJECTED shares with beg
bfg REJECTED shares with afg
bfh ACCEPTED not shared with ['abc', 'acd', 'ade', 'aef', 'afg', 'agh',
'ahi', 'bdf', 'beg']
bfi REJECTED shares with bfh
bgh REJECTED shares with agh
bgi ACCEPTED not shared with ['abc', 'acd', 'ade', 'aef', 'afg', 'agh',
'ahi', 'bdf', 'beg', 'bfh']
bhi REJECTED shares with ahi
cde REJECTED shares with acd
cdf REJECTED shares with acd
cdg REJECTED shares with acd
cdh REJECTED shares with acd
cdi REJECTED shares with acd
cef REJECTED shares with aef
ceg REJECTED shares with beg
ceh ACCEPTED not shared with ['abc', 'acd', 'ade', 'aef', 'afg', 'agh',
'ahi', 'bdf', 'beg', 'bfh', 'bgi']
cei REJECTED shares with ceh
cfg REJECTED shares with afg
cfh REJECTED shares with bfh
cfi ACCEPTED not shared with ['abc', 'acd', 'ade', 'aef', 'afg', 'agh',
'ahi', 'bdf', 'beg', 'bfh', 'bgi', 'ceh']
cgh REJECTED shares with agh
cgi REJECTED shares with bgi
chi REJECTED shares with ahi
def REJECTED shares with ade
deg REJECTED shares with ade
deh REJECTED shares with ade
dei REJECTED shares with ade
dfg REJECTED shares with afg
dfh REJECTED shares with bdf
dfi REJECTED shares with bdf
dgh REJECTED shares with agh
dgi REJECTED shares with bgi
dhi REJECTED shares with ahi
efg REJECTED shares with aef
efh REJECTED shares with aef
efi REJECTED shares with aef
egh REJECTED shares with agh
egi REJECTED shares with beg
ehi REJECTED shares with ahi
fgh REJECTED shares with afg
fgi REJECTED shares with afg
fhi REJECTED shares with ahi
ghi REJECTED shares with agh
>>>
>>> len(accepted)
13
>>> accepted
['abc', 'acd', 'ade', 'aef', 'afg', 'agh', 'ahi', 'bdf', 'beg', 'bfh',
'bgi', 'ceh', 'cfi']
>>>
Note that this passes 13 triplets, one more than the 12 you imply.
--
Wulfraed Dennis Lee Bieber AF6VN
wlfraed at ix.netcom.com http://wlfraed.microdiversity.freeddns.org/
More information about the Tutor
mailing list