[Tutor] problem solving with lists

[marcus.luetolf at bluewin.ch]

Hello Experts again,
I was a couple days away from my computer and had ample time to rethink my
problem computationally,
since my previous approach below is bound to a dead end:

As a remark in between: 
° all_letters = 'abcdefghi' instead of all_letters = list('abcdefghi') threw
an error.
° The problem with 6  instead of 9 letters cannot be solved for mathematical
reasons (below).

Problem description:
Distribute  letters (or items) of a list of n letter (or items) to sublists
containig r letters (or items)
in a manner that pairs of letters, p.e. 'a', 'b' or 'd', 'f' can occur only
once.
As a border or constraint  r can only be 3 or 4 and a solution requires (n -
1)  % ( r - 1) == 0.

Algorithm for n = 9, r = 3:
1. Step: Create sublists of all possible combinations of letters
[['a','a','a'], ['a', 'a', 'b'].......['i', 'i', 'i']], a total of 9^3 = 729
sublists.
2. Step: Remove all sublists containing the same letter more than once.
3. Step: Sort all remaining sublists.
4. Step: Remove all duplicates.

These four steps can accomplished by  itertools funcion combinations:

>from itertools import combinations

>iterable = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i']
>r = 3
>all_tuples = list(combinations(iterable, 3))

>all_sub_lists = []
>for i in all_tuples:
    >all_sub_lists.append(list(i))

>print(all_sub_lists, len(all_sub_lists))

yielding 84 sublists. Using not paper and pencil but Excel I got the same
number.

5. and most crucial step: Remove all sublists containing duplicates of pairs
of letters:
P.e. if pairs of sublist[0]and  sublist[1], or sublist[0] and sublist[2] or
sublist[1] and sublist[2] were 
already seen, remove that sublist. There should result 12 sublists.

It's that last step I struggle with and which would allow to apply the
algorithm for n = 16 and r = 4, 
my final problem or further. I possibly could do it by hand but not for n =
16, r = 4 (1820 sublists !)
Appreciate any help, Marcus.

-----Ursprüngliche Nachricht-----
Von: Tutor <tutor-bounces+marcus.luetolf=bluewin.ch at python.org> Im Auftrag
von Alan Gauld via Tutor
Gesendet: Montag, 7. März 2022 12:24
An: tutor at python.org
Betreff: Re: [Tutor] problem solving with lists

On 07/03/2022 07:44, marcus.luetolf at bluewin.ch wrote:

> I should have written ... c) if my problem can by solved with python 
> or any other programming language at all.

Python, or any other "Turing complete" programming language can represent
any algorithm you come up with. So the answer is yes, once you have the
algorithm.

> It's the process of finding an algorithm to solve my task I am stuck 
> with

And that is often the hardest bit.

> I'am very gratefull for your advice to reduce the task to 9 
> items/letters in sublists of 3 (soem sort of recursion ?) but it 
> doesn't get me any further.

Can you solve it by hand? - ie. using a pencil and paper.
If not then you don't really understand your problem yet.
So you need to write down all the different conditions that must be met,
including all the exceptional cases that might arise.

Once you understand what needs to be done you should be able to work out how
to do it using pencil and paper.

That will give you an algorithm. It may not be the most efficient, and it
will likely not be generalized to "N sublists from M" elements yet. But it
is a start.

But unless you understand the solution at that level you are unlikely to be
able to write a program to solve it. (Unless it's a swell known algorithm
and you can find a library. But it looks as if your requirements are
slightly different from the more common cases)

We can certainly help you formulate the required algorithm, and possibly
some shortcuts. But you need to give us a complete and precise description
of the problem.

--
Alan G
Author of the Learn to Program web site
http://www.alan-g.me.uk/
http://www.amazon.com/author/alan_gauld
Follow my photo-blog on Flickr at:
http://www.flickr.com/photos/alangauldphotos


_______________________________________________
Tutor maillist  -  Tutor at python.org
To unsubscribe or change subscription options:
https://mail.python.org/mailman/listinfo/tutor