Fractionnement et indexation récursifs de listes

Question

J'ai écrit le code suivant pour diviser la liste de manière récursive. Il divise d'abord le côté gauche de manière récursive jusqu'à ce qu'il ne reste plus qu'un seul élément.

Code :

def split(class_names):

  while len(class_names)>1:
    n=len(class_names)
    mid=n//2
    left=class_names[:mid]
    right=class_names[mid:]
    splits.append([left,right])
    class_names=left
    index=1
    split(left)
    class_names=right
  return splits
class_names=[1,2,3,4,5,6,7,8,9,10]
splits=[]
splits=split(class_names)

for ii in splits:
  print(ii)

Sortie :

[[1, 2, 3, 4, 5], [6, 7, 8, 9, 10]]
[[1, 2], [3, 4, 5]]
[[1], [2]]
[[3], [4, 5]]
[[4], [5]]
[[6, 7], [8, 9, 10]]
[[6], [7]]
[[8], [9, 10]]
[[9], [10]]

Problème : J'ai besoin de cette information sous la forme d'un arbre et de son index. Le côté gauche doit ajouter 0 à la fin et le côté droit doit ajouter 1 à la fin. Par exemple, le côté gauche doit ajouter 0 à la fin et le côté droit doit ajouter 1 à la fin :

                 [[1, 2, 3, 4, 5], [6, 7, 8, 9, 10]]
                            /\
                        0  /  \ 1
          [[1, 2], [3, 4, 5]]  [[6, 7], [8, 9, 10]]
                /\
            0  /  \ 1
       [[1], [2]]  [[3], [4, 5]]
Then the output should be like:
[[1, 2, 3, 4, 5], [6, 7, 8, 9, 10]] = 0
[[1, 2], [3, 4, 5]] = 00
[[6, 7], [8, 9, 10]] = 01
[[1], [2]] = 000

Answer 1

Vous avez maîtrisé la récursivité, mais vous devez suivre l'index au fur et à mesure que vous vous déplacez de gauche à droite. Voici un moyen avec un paramètre supplémentaire, et réécrit comme un générateur :

def split(class_names, index='0'):
    if (n := len(class_names)) < 2:
        return
    mid = n // 2
    left, right = class_names[:mid], class_names[mid:]
    yield [left, right], index
    yield from split(left, index + '0')
    yield from split(right, index + '1')

class_names = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
for node, index in split(class_names):
    print(f'{node} = {index}')

Sortie :

[[1, 2, 3, 4, 5], [6, 7, 8, 9, 10]] = 0
[[1, 2], [3, 4, 5]] = 00
[[1], [2]] = 000
[[3], [4, 5]] = 001
[[4], [5]] = 0011
[[6, 7], [8, 9, 10]] = 01
[[6], [7]] = 010
[[8], [9, 10]] = 011
[[9], [10]] = 0111