{"id":1854,"date":"2024-04-27T12:44:00","date_gmt":"2024-04-27T11:44:00","guid":{"rendered":"https:\/\/blog.univ-angers.fr\/mathsinfo\/?p=1854"},"modified":"2024-04-27T18:58:54","modified_gmt":"2024-04-27T17:58:54","slug":"rpn-recherche-de-permutations","status":"publish","type":"post","link":"https:\/\/blog.univ-angers.fr\/mathsinfo\/2024\/04\/27\/rpn-recherche-de-permutations\/","title":{"rendered":"RPN : Recherche de permutations"},"content":{"rendered":"\n

On trouve, dans certains ouvrages sur les calculatrices HP, des tables donnant les combinaisons de touches pour r\u00e9ordonner les \u00e9l\u00e9ments de la pile XYZT :<\/p>\n\n\n

\n
\"\"<\/a><\/figure>\n<\/div>\n\n\n

Par exemple ci-dessus, ligne n\u00b09, si ABCD<\/strong> sont sur la pile XYZT<\/strong>, la combinaison x><y, CLX<\/strong> et ENTER<\/strong> permettra d’avoir 00AC<\/strong> sur la pile.<\/p>\n\n\n\n

L’id\u00e9e m’est venue de faire la m\u00eame chose pour les calculatrices HP-48\/49\/50g qui ont d’autres commandes pour manipuler la pile.<\/p>\n\n\n\n

A partir d’\u00e9l\u00e9ments (e1<\/strong> au niveau 1, e2<\/strong> au niveau 2 etc.), on voudrait les r\u00e9ordonner en utilisant les commandes de base du langage RPN : DUP, SWAP, DROP, OVER, ROT, DUP2, DROP2<\/strong> et PICK3<\/strong>.<\/p>\n\n\n\n

Exemples :<\/p>\n\n\n\n

La pile contient uniquement 2 \u00e9l\u00e9ments e1<\/strong> (niveau 1) et e2<\/strong> (niveau 2)et on veut les inverser<\/em>. R\u00e9ponse : SWAP<\/strong><\/p>\n\n\n\n

La pile contient 3 \u00e9l\u00e9ments e1 : e2 : e3<\/strong> et on veut inverser les \u00e9l\u00e9ments des niveaux 2 et 3 pour obtenir e1 : e3 : e2<\/strong>. R\u00e9ponse : ROT SWAP<\/strong><\/p>\n\n\n\n

Je vous propose un petit programme Python qui fait une recherche brute de toutes les possibilit\u00e9s (en partant des combinaisons \u00e0 1 commandes, puis \u00e0 2 commandes etc. Avec r\u00e9p\u00e9titions, par exemple OVER OVER<\/strong>). Il recherche jusqu’\u00e0 une combinaison de 7 commandes ce qui peut demander du temps !<\/p>\n\n\n\n

Tester le programme en ligne<\/a><\/p>\n\n\n\n

from itertools import *\n\nkeys = \"DUP\", \"SWAP\", \"DROP\", \"OVER\", \"ROT\", \"DUP2\", \"DROP2\", \"PICK3\"\n\ndef DUP(s): return [s[0]] + s if len(s)>0 else -1\ndef SWAP(s): return [s[1], s[0]] + s[2:] if len(s) > 1 else -1\ndef DROP(s): return s[1:] if len(s) > 0 else -1\ndef OVER(s): return [s[1]] + s if len(s) > 1 else -1\ndef ROT(s): return [s[2]] + s[:2] +s[3:] if len(s) > 2 else -1\ndef DUP2(s): return [s[0], s[1]] + s if len(s) > 1 else -1\ndef DROP2(s): return s[2:] if len(s) > 2 else -1\ndef PICK3(s): return [s[2]] + s if len(s) > 2 else -1\n\ndef find(target, n):\n rr = [1 + v for v in range(n)]\n tr = [int(v) for v in target]\n for n in range(1, 8):\n  for op in combinations_with_replacement(keys, n):\n   for p in permutations(op):\n    r = rr\n    for c in p:\n     t = eval(c)(r)\n     if t == -1: break\n     r = t\n    if r == tr:\n     rs = ':'.join([str(v) for v in rr])\n     return '{} -> {} = {}'.format(rs, ':'.join(list(target)), \" \/ \".join(p))\n\n return \"No solution\"\n\n# 5 levels on the stack (e1:e2:e3:e4:e5). Goal : e2:e2\n>>> find(\"22\", 5)\n'1:2:3:4:5 -> 2:2 = ROT \/ DROP2 \/ SWAP \/ ROT \/ DROP2 \/ DUP'\n\n# 3 levels on the stack (e1:e2:e3). Goal : e1:e2:e3:e1:e2:e3\n>>> find(\"123123\", 3)\n'1:2:3 -> 1:2:3:1:2:3 = PICK3 \/ PICK3 \/ PICK3'\n\n# 3 levels on the stack. Goal : e1:e1:e2:e2:e3:e3\n>>> find(\"112233\", 3)\n'1:2:3 -> 1:1:2:2:3:3 = PICK3 \/ ROT \/ ROT \/ DUP2 \/ ROT'\n\n# 4 levels on the stack. Goal : e2:e2:e4:e4\n>>> find(\"2244\", 4)\n'1:2:3:4 -> 2:2:4:4 = ROT \/ DROP2 \/ DUP2 \/ ROT'<\/code><\/pre>\n\n\n\n
Version pour la HP-50g<\/h2>\n\n\n\n
Cette calculatrice a plus de commandes que les HP-48G pour manipuler la pile, j’ajoute DUPDUP<\/strong>, UNROT<\/strong> et 4 ROLL<\/strong> (comme ROT<\/strong> mais avec le niveau 4)<\/p>\n\n\n\n
from itertools import *\n\n# Version HP-50g\n\nkeys = \"DUP\", \"DUPDUP\",\"SWAP\", \"DROP\", \"OVER\", \"ROT\", \"UNROT\", \"DUP2\", \"DROP2\", \"PICK3\", \"_4_ROLL\"\n\ndef DUP(s): return [s[0]] + s if len(s)>0 else -1\ndef DUPDUP(s): return [s[0], s[0]] + s if len(s)>0 else -1\ndef SWAP(s): return [s[1], s[0]] + s[2:] if len(s) > 1 else -1\ndef DROP(s): return s[1:] if len(s) > 0 else -1\ndef OVER(s): return [s[1]] + s if len(s) > 1 else -1\ndef ROT(s): return [s[2]] + s[:2] +s[3:] if len(s) > 2 else -1\ndef UNROT(s): return s[1:3] + [s[0]] +s[3:] if len(s) > 2 else -1\ndef DUP2(s): return [s[0], s[1]] + s if len(s) > 1 else -1\ndef DROP2(s): return s[2:] if len(s) > 2 else -1\ndef PICK3(s): return [s[2]] + s if len(s) > 2 else -1\ndef _4_ROLL(s): return [s[3]] + s[:3] +s[4:] if len(s) > 3 else -1\n\ndef find(target, n):\n rr = [1 + v for v in range(n)]\n tr = [int(v) for v in target]\n for n in range(1, 8):\n  for op in combinations_with_replacement(keys, n):\n   for p in permutations(op):\n    r = rr\n    for c in p:\n     t = eval(c)(r)\n     if t == -1: break\n     r = t\n    if r == tr:\n     rs = ':'.join([str(v) for v in rr])\n     return '{} -> {} = {}'.format(rs, ':'.join(list(target)), \" \/ \".join(p))\n\n return \"No solution\"\n\n>>> find(\"231\", 3)\n'1:2:3 -> 2:3:1 = UNROT'\n\n>>> find(\"4123\", 4)\n'1:2:3:4 -> 4:1:2:3 = _4_ROLL'\n\n>>> find(\"135\", 5)\n'1:2:3:4:5 -> 1:3:5 = SWAP \/ _4_ROLL \/ DROP2'\n\n>>> find(\"4321\", 4)\n'1:2:3:4 -> 4:3:2:1 = SWAP \/ ROT \/ _4_ROLL'\n<\/code><\/pre>\n\n\n\n
Version en PROLOG (en cours de r\u00e9alisation)<\/h2>\n\n\n\n
% R\u00e8gles pour les op\u00e9rations sur la pile\n\n% SWAP : Inverse les niveaux 1 et 2\nswap([A,B|T], [B,A|T]).\n\n% DUP : Duplique le niveau 1\ndup([A|T], [A,A|T]).\n\n% DROP : Supprime le niveau 1\ndrop([_|T], T).\n\n% OVER : R\u00e9cup\u00e8re le niveau 2 et le met au niveau 1\nover([A,B|T], [B,A,B|T]).\n\n% ROT\nrot([A,B,C|T], [C,A,B|T]).\n\n\n% R\u00e8gle pour arr\u00eater la r\u00e9cursivit\u00e9 lorsque la pile est d\u00e9j\u00e0 dans l'\u00e9tat voulu\ntrouve([], Stack, Stack).\n\n% R\u00e8gles pour trouver la s\u00e9quence d'op\u00e9rations \n\ntrouve([swap|Actions], Stack, FinalState) :-\n    swap(Stack, NewStack),\n    trouve(Actions, NewStack, FinalState).\n\ntrouve([dup|Actions], Stack, FinalState) :-\n    dup(Stack, NewStack),\n    trouve(Actions, NewStack, FinalState).\n\ntrouve([drop|Actions], Stack, FinalState) :-\n    drop(Stack, NewStack),\n    trouve(Actions, NewStack, FinalState).\n\ntrouve([over|Actions], Stack, FinalState) :-\n    over(Stack, NewStack),\n    trouve(Actions, NewStack, FinalState).\n\ntrouve([rot|Actions], Stack, FinalState) :-\n    rot(Stack, NewStack),\n    trouve(Actions, NewStack, FinalState).\n<\/code><\/pre>\n\n\n\n
Quelques tests<\/p>\n\n\n\n
rot([1,4,3],X).\nR\u00e9ponse : X = [3, 1, 4]\n\nswap([1,4,3],X).\nR\u00e9ponse : X = [4, 1, 3]\n\ndrop([1,4,3],X).\nR\u00e9ponse : X = [4, 3]\n\nover([1,4,3],X).\nR\u00e9ponse : X = [4, 1, 4, 3]\n\ntrouve(X, [1,4,3], [4,1,3]).\nX = [swap]\n\n<\/code><\/pre>\n\n\n\n
Version 2 propos\u00e9e par chatGPT<\/h2>\n\n\n\n
trouve(Actions, Stack, FinalState) :-\n    trouver_sequence(Actions, [], Stack, FinalState).\n\n% Cas o\u00f9 l'\u00e9tat actuel est l'\u00e9tat voulu\ntrouver_sequence([], _, Stack, Stack).\n\n% Cas o\u00f9 l'\u00e9tat actuel est diff\u00e9rent de l'\u00e9tat voulu, continue \u00e0 chercher\ntrouver_sequence([Action|Actions], History, CurrentState, FinalState) :-\n    \\+ member(CurrentState, History), % V\u00e9rifie si l'\u00e9tat actuel a d\u00e9j\u00e0 \u00e9t\u00e9 visit\u00e9 pour \u00e9viter les boucles infinies\n    apply_action(Action, CurrentState, NextState),\n    trouver_sequence(Actions, [CurrentState|History], NextState, FinalState).\n\n% Applique une action sur l'\u00e9tat actuel de la pile\napply_action(swap, [A,B|T], [B,A|T]).\napply_action(dup, [A|T], [A,A|T]).\napply_action(drop, [_|T], T).\napply_action(over, [A,B|T], [B,A,B|T]).\napply_action(rot, [A,B,C|T], [C,A,B|T]).<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"
On trouve, dans certains ouvrages sur les calculatrices HP, des tables donnant les combinaisons de touches pour r\u00e9ordonner les \u00e9l\u00e9ments de la pile XYZT : Par exemple ci-dessus, ligne n\u00b09, si ABCD sont sur la pile XYZT, la combinaison x><y, … Continuer la lecture →<\/span><\/a><\/p>\n","protected":false},"author":4913,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"class_list":["post-1854","post","type-post","status-publish","format-standard","hentry","category-non-classe"],"_links":{"self":[{"href":"https:\/\/blog.univ-angers.fr\/mathsinfo\/wp-json\/wp\/v2\/posts\/1854","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blog.univ-angers.fr\/mathsinfo\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blog.univ-angers.fr\/mathsinfo\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blog.univ-angers.fr\/mathsinfo\/wp-json\/wp\/v2\/users\/4913"}],"replies":[{"embeddable":true,"href":"https:\/\/blog.univ-angers.fr\/mathsinfo\/wp-json\/wp\/v2\/comments?post=1854"}],"version-history":[{"count":12,"href":"https:\/\/blog.univ-angers.fr\/mathsinfo\/wp-json\/wp\/v2\/posts\/1854\/revisions"}],"predecessor-version":[{"id":1868,"href":"https:\/\/blog.univ-angers.fr\/mathsinfo\/wp-json\/wp\/v2\/posts\/1854\/revisions\/1868"}],"wp:attachment":[{"href":"https:\/\/blog.univ-angers.fr\/mathsinfo\/wp-json\/wp\/v2\/media?parent=1854"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blog.univ-angers.fr\/mathsinfo\/wp-json\/wp\/v2\/categories?post=1854"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blog.univ-angers.fr\/mathsinfo\/wp-json\/wp\/v2\/tags?post=1854"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}