Permutation, recursion made by IterationList - Study
- Author:
- hawe
- Topic:
- Combinatorics
A simple way to permutations
A simple idea is to use permutations of n-1 elements to generate permutations of n elements.
Generate permutations of size 3 using permutations of size 2.
Permutations of two elements 1 2 and 2 1.
Permutations of three elements can be obtained by inserting 3 at all positions in all permutations of size 2.
Inserting 3 in all positions of 1 2 ===> 1 2 3, 1 3 2 and 3 1 2.
Inserting 3 in all positions of 2 1 ===> 2 1 3, 2 3 1 and 3 2 1.
n=3
Iteration({Element(a, 1)+1,Join(Sequence( (Sequence(Insert({Element(a, 1)+1}, Element(Element(a, 2),k) ,j ),j,Element(a, 1) +1,1,-1)),k,1,Length(Element(a, 2))))}, a, {{ 1,{ {1}} }} , n-1)
Iteration({N(X)+1,Join(Sequence( (Sequence(Insert({N(X)+1}, Element(P(X),k) ,j ),j,N(X) +1,1,-1)),k,1, (N(X)! )))}, X, {{ 1,{ {1}} }} , n-1) mit N(p):=Element(p, 1), P(p):=Element(p, 2)
Iteration( «Expression», «Variables», «Start Values», «Count» )
IterationList({Element(a,1) + 1, …..(Element(a,2), Element(a,1) + 1)…..},a,{{0, A0}},3)
j ( A j )
Rekursion, wenn für Expression und Laufvariable a eine spezielle Listenform gewählt wird:
«Variables», «Start Values» == a , {{0, A0}}
j == Element(a,1) Element(a,2) == Aj-1
use IterationList() to see all the growing permutation steps.
to trace n times n-1 lists of permutation let grow up iteration count going thru all n permutation. stops at P6 - P7 (ggb6.x), CAS 
, AlgebraView:
is there a limit of list lenght?
, AlgebraView:
is there a limit of list lenght?
https://de.wikipedia.org/wiki/Heap-Algorithmus
| var n = 4; var A = []; var c = []; ggbApplet.evalCommand("Ljs={{1},{1},{1}}"); // c ist eine Codierung des Stapelzustands. c[k] codiert den Schleifen-Zähler, wenn generate(k - 1, A) aufgerufen wird for (var i = 0; i < n; i++) { c[i] = 0; A[i] = i + 1; }; ggbApplet.evalCommand("Ljs={{" + A + "}}"); var k = 1; var i = 1; while (i < n) { if (c[i] < i) { if (i % 2 == 0) { var t = A[0]; A[0] = A[i]; A[i] = t; } else { var t = A[c[i]]; A[c[i]] = A[i]; A[i] = t; }; k++; ggbApplet.evalCommand("SetValue(Ljs," + (k) + ",{" + A + "})"); // Vertauschung ist durchgeführt worden und hat die Schleife beendet. Simuliert das Inkrement des Schleifen-Zählers c[i]++; // Simuliert einen rekursiven Aufruf, der den Basisfall erreicht, indem der Zeiger auf den Basisfall analog im Array durchgeführt wird i = 1; } else { // das Aufrufen von generate(i+1, A) endet, wenn die Schleife endet. // Setzt den Status zurück und simuliert das Stapeln durch Inkrementieren des Zeigers. c[i] = 0; i++; }; }; | Javascript translation from wiki article I have tried to create permutations via IterationList. An implementation of the heap algorithm (-> Wikipedia). It is clear that this doesn't get you very far, because the lists grow factorially. More out of interest for investigating or exercise IterationList.... Now there are iteration steps that only transfer the heap pointers and do not bring the permutation further. -this else statement - you can filter the IterationList out unique but the iteration list grows and the additional overhead is not predictable for me... |
Start_i={HeapPointer,{Heap},{Permutation}}
N_i=IterationCount
HeapPointer, Element(a,1)
{Heap}, Element(a,2)
{Permutation}, Element(a,3)
P_{Heap}=
IterationList(
If(Element(Element(a, 2), Element(a, 1)) < Element(a, 1),
{2, Sequence(Element(Element(a, 2), j) + (Element(a, 1) ≟ j) * 1, j, 1, Length(Element(a, 2))),
If(Mod(Element(a, 1) - 1, 2) ≟ 0,
Sequence(Element(Element(a, 3), If(j ≟ 1, Element(a, 1), If(j ≟ Element(a, 1), 1, j))), j, 1, Length(Element(a, 2))),
Sequence(Element(Element(a, 3),
If(j ≟ Element(Element(a, 2), Element(a, 1)), Element(a, 1), If(j ≟ Element(a, 1), Element(Element(a, 2), Element(a, 1)), j))), j, 1,
Length(Element(a, 2))))},
{Element(a, 1) + 1, Sequence(If(Element(a, 1) ≟ j, 1, Element(Element(a, 2), j)), j, 1, Length(Element(a, 2))), Element(a, 3)}),
a, {Start_i}, N_i)
Permute=Unique(Sequence(Element(P_{Heap}, j, 3), j, 1, Length(P_{Heap})))
wikiheaplist=Sequence({Element(l1, j, 1) - 1, Element(l1, j, 2) - 1, Element(l1, j, 3)}, j, 2, Length(l1))
P3={2, {1, 1, 1}, {1, 2, 3}} 3!=6, N_i=7
P4={2, {1, 1, 1, 1}, {1, 2, 3, 4}}, Ni=30, 4!=24
P5={2, {1, 1, 1, 1, 1}, {1, 2, 3, 4, 5}}, Ni=180, 5!=120
P6={2, {1, 1, 1, 1, 1, 1}, {1, 2, 3, 4, 5, 6}}, Ni=1133, 6!=720
P7 = ? unstable, Ni~8000, 7!=5040
- perhaps you will create the permutation list piecewise doing a reasonable list length count Ni, copy the last Iteration step of heap list and start (Starti) a new list with it ;-)P(Start_i, N_i), CAS user-function
Zyklen, Tupel, Ketten-Hintereinanderausführung
Iteration-Examples
IterationList[{Element[a, 1] + 1, Element[a, 2] + (Element[a, 1] + 1)² + 2}, a, {{1, 4}}, 10]
IterationList({Element(a, 1) + 1, ((Element(a, 1) + 1) * Element(a, 2) + 3(Element(a, 1) + 1)!) / 2}, a, {{1, 3}}, 10)
Fibonacci:=Iteration(Join({a, {Element(a, Length(a) - 1) + Element(a, Length(a))}}), a, {{1, 1}}, 12)
Fibonacci:=Iteration(Join(a, {Sum(Take(a, Length(a) - 1))} ), a, {{1, 1}}, 12)
CAS-Function LU Decomposition at one single matrix
LR Zerlegung auf einem Matrixfeld
LRdecomp(AA,k):=Join(Take(AA,1,k), Sequence(Sequence(If(i < k,Element(AA, j,i) , If(i==k,Element(AA, j,k)/Element(AA, k,k), Element(AA, j,i) -Element(AA,j,k) (Element(AA, k,i)/Element(AA, k,k)))) ,i,1,Length(AA)) ,j,k+1,Length(AA)));
(12) A:= {{2,1,-3,4},{4,1,-4,9},{-2,1,0,-5},{2,2,-5,1}}
(13) IterationList({Element(a,1)+1,LRdecomp(Element(a, 2),Element(a, 1)+1) }, a, {{0, A}},3)
Intervall-Schachtelung nach Heron
(1) Y:=3
(2) Numeric(IterationList({2 Y /Sum(X), Sum(X)/2}, X, {{1,Y}},5),15)
(3) Flatten(Last($2)) - sqrt(Y)
Folgen explizit - rekursiv
Folgen expliziter Darstellung
(1) an = 1/n ; n>=1 : Sequence(1/n ,n,1,11)
(2) an=n-3 ; n>= 1 : Sequence(n-3,n,1,15)
(3) an= n/(n+1) ; n>= 1 : Sequence(n/(n+1),n,1,11)
in rekursiver Schreibweise
(1) IterationList( 1/(1/a+1) ,a,{1},10)
(2) IterationList(a+1,a,{(-2) },15)
(3) IterationList( -1/(a-2) ,a,{1/2},10) 1/(1+1/(1+1/(1/a-1)))
Verfahren
(1) .
Das nächste Folgeglied
.
Ersetze durch und erhalte
.
hängt nur noch vom Vorgänger ab .
Javascript
function an(x) {
if (x > 1 / 11) an(1 / (1 / x + 1))
alert(x);
}