Permutations by swapping: Difference between revisions

Content added Content deleted

Inline

@@ Line 2,333: / Line 2,333: @@
 =={{header|PowerShell}}==
 <lang PowerShell>
-function permutation ($array) {
+function output([Object[]]$A, [Int]$k, [ref]$sign)
+{
-    function sign($A) {
+    "Perm: [$([String]::Join(', ', $A))] Sign $($sign.Value) `n"
-        $size = $A.Count
+}
-        $sign = 1
-        for($i = 0; $i -lt $size; $i++) {
+function permutation ($array)
-            for($j = $i+1; $j -lt $size ; $j++) {
+{
-                if($A[$j] -lt $A[$i]) { $sign *= -1}
+    function generate([Object[]]$A, [Int]$k, [ref]$sign)
-            }
-        }
+    {
-        $sign
+        if($k -eq 1)
-    }
+        {
-    function generate($n, $A, $i1, $i2, $cnt) {
+            output $A $k $sign
-        if($n -eq 1) {
+            $sign.Value = -$sign.Value
-            if($cnt -gt 0) {
-                "$A -- swapped positions: $i1 $i2 -- sign = $(sign $A)`n"
-            } else {
-                "$A -- sign = $(sign $A)`n"
-            }
         }
-        else{
+        else
+        {
-            for( $i = 0; $i -lt ($n - 1); $i += 1) {
-                generate ($n - 1) $A $i1 $i2 $cnt
+            generate $A  ($k - 1) $sign
-                if($n % 2 -eq 0){
+            for([Int]$i = 0; $i -lt $k - 1; $i += 1)
-                    $i1, $i2 = $i, ($n-1)
+             {
-                    $A[$i1], $A[$i2] = $A[$i2], $A[$i1]
+                if($i % 2 -eq 0)
-                    $cnt = 1
+                {
+                    $A[$i], $A[$k - 1] = $A[$k - 1], $A[$i]
                 }
-                else{
+                else
-                    $i1, $i2 = 0, ($n-1)
+                {
-                    $A[$i1], $A[$i2] = $A[$i2], $A[$i1]
+                    $A[0], $A[$k - 1] = $A[$k - 1], $A[0]
-                    $cnt = 1
                 }
+                generate $A ($k - 1) $sign
             }
-            generate ($n - 1) $A $i1 $i2 $cnt
         }
     }
-    $n = $array.Count
+    generate $array $array.Count ([ref]1)
-    if($n -gt 0) {
-        (generate $n $array  0 ($n-1) 0)
-    } else {$array}
 }
-permutation @(1,2,3,4)
+permutation @(0, 1,2,3)
 </lang>
 <b>Output:</b>
 <pre>
-2 3 4 -- sign = 1
+Perm: [0, 1, 2, 3] Sign 1
+Perm: [1, 0, 2, 3] Sign -1
-1 3 4 -- swapped positions: 0 1 -- sign = -1
+Perm: [2, 0, 1, 3] Sign 1
-1 2 4 -- swapped positions: 0 2 -- sign = 1
+Perm: [0, 2, 1, 3] Sign -1
-3 2 4 -- swapped positions: 0 1 -- sign = -1
+Perm: [1, 2, 0, 3] Sign 1
-3 1 4 -- swapped positions: 0 2 -- sign = 1
+Perm: [2, 1, 0, 3] Sign -1
-2 1 4 -- swapped positions: 0 1 -- sign = -1
+Perm: [3, 1, 0, 2] Sign 1
-2 1 3 -- swapped positions: 0 3 -- sign = 1
-4 1 3 -- swapped positions: 0 1 -- sign = -1
+Perm: [1, 3, 0, 2] Sign -1
+Perm: [0, 3, 1, 2] Sign 1
-4 2 3 -- swapped positions: 0 2 -- sign = 1
-1 2 3 -- swapped positions: 0 1 -- sign = -1
+Perm: [3, 0, 1, 2] Sign -1
+Perm: [1, 0, 3, 2] Sign 1
-1 4 3 -- swapped positions: 0 2 -- sign = 1
-2 4 3 -- swapped positions: 0 1 -- sign = -1
+Perm: [0, 1, 3, 2] Sign -1
-3 4 2 -- swapped positions: 1 3 -- sign = 1
+Perm: [2, 1, 3, 0] Sign 1
+Perm: [1, 2, 3, 0] Sign -1
-1 4 2 -- swapped positions: 0 1 -- sign = -1
+Perm: [3, 2, 1, 0] Sign 1
-1 3 2 -- swapped positions: 0 2 -- sign = 1
+Perm: [2, 3, 1, 0] Sign -1
-4 3 2 -- swapped positions: 0 1 -- sign = -1
+Perm: [1, 3, 2, 0] Sign 1
-4 1 2 -- swapped positions: 0 2 -- sign = 1
-3 1 2 -- swapped positions: 0 1 -- sign = -1
+Perm: [3, 1, 2, 0] Sign -1
+Perm: [3, 1, 0, 2] Sign 1
-3 2 1 -- swapped positions: 2 3 -- sign = 1
+Perm: [1, 3, 0, 2] Sign -1
-4 2 1 -- swapped positions: 0 1 -- sign = -1
+Perm: [0, 3, 1, 2] Sign 1
-4 3 1 -- swapped positions: 0 2 -- sign = 1
-2 3 1 -- swapped positions: 0 1 -- sign = -1
+Perm: [3, 0, 1, 2] Sign -1
+Perm: [1, 0, 3, 2] Sign 1
-2 4 1 -- swapped positions: 0 2 -- sign = 1
-3 4 1 -- swapped positions: 0 1 -- sign = -1
+Perm: [0, 1, 3, 2] Sign -1
 </pre>