Suite de Robinson
Suites de Robinson : suite mathématique dont chaque terme se détermine en comptant combien de fois chaque chiffre apparaît dans le terme précédent.
Je renvoie vers Misez p’tit, Optimisez – N°15 (le jour des fourmis) pour plus d’explications sur cette suite.
En APL :
ROB ← {⊃ (+⌿ ⍵ ∘.∊ n) ,., n ← ∪⍵}
ROB 0
Output : 1 0 ⍝ Il y a 1 zéro
ROB 1 0
Output : 1 1 1 0 ⍝ 1 un et 1 zéro
(ROB ⍣ 10) 0 ⍝ Pour répéter 10 fois
Output : 3 3 2 2 1 4 3 1 1 0
Explications :
∪⍵ : On récupère les valeurs uniques du vecteur
⍵ ∘.∊ n : Matrice pour les tests d’appartenance (produit externe)
v ← 1 3 2 1 1 0 ⍝ Exemple de vecteur ∪ v ⍝ Eléments uniques Output : 1 3 2 0 v ∘.∊ ∪ v ⍝ Matrice d'appartenance 1 0 0 0 ⍝ Positions des éléments 0 1 0 0 ⍝ du vecteur 1 3 2 1 1 0 0 0 1 0 ⍝ dans le vecteur 1 3 2 0 1 0 0 0 1 0 0 0 0 0 0 1
+⌿ : Somme des différentes colonnes
+⌿ v ∘.∊ ∪v 3 1 1 1
,., : Double concaténation, déjà entre les sommes et les éléments de ∪v puis concaténation de l’ensemble.
Nous allons créer un programme RPL en utilisant UN. (union) et PE. (Produit externe) que l’on a vus précédemment. Plus précisément nous obtiendrons :
1: {1} # on part de 1 zéro
2: {0}
VAR ROB
1: {1 1}
2: {0 1} # 1 zéro et 1 un
ROB
1: {1 3}
2: {0 1} # 1 zéro et 3 un
ROB
1: {1 2 1}
2: {0 1 3} # 1 zéro, 2 un et 1 trois
...
ROB
1: {1 3 2 3 1}
2: {0 1 2 3 4} # La suite stationne
Idée du programme : on concatène les 2 listes (+), puis on la duplique (DUP) et on cherche les éléments uniques (UN.)
Ensuite on va créer la matrice d’appartenance, par exemple en utilisant « – NOT ». L’idée étant de soustraire du vecteur (niveau 1 ci-dessous) la valeur que l’on cherche. En appliquant NOT les 0 se transforment en 1 et les valeurs non nulles en 0. Le problème est que « == » ou « SAME » ne fonctionnent pas avec PE. d’où cette “astuce”.
2: { 1 2 }
1: { 1 1 1 2 2 1 2 }
« - NOT »
VAR PE.
1: {{1 1 1 0 0 1 0} {0 0 0 1 1 0 1}}
On a les endroits où apparaissent 1 et 2 dans le vecteur 1 1 1 2 2 1 2
Il suffit ensuite de faire les sommes des différentes listes (∑LIST) :
2: { 1 2 }
1: { 1 1 1 2 2 1 2 }
« - NOT ∑LIST»
VAR PE.
1: {4 3}
on obtient finalement :
« + DUP UN. SORT DUP ROT « - NOT ∑LIST » PE. SWAP » 'ROB STO