Topswops: Difference between revisions

{{trans|Python:_Faster_Version}}

 

 

F try_swaps(&deck, f, =s, d, n)

 

L(i) 1..12

 

{{out}}

=={{header|360 Assembly}}==

The program uses two ASSIST macro (XDECO,XPRNT) to keep the code as short as possible.

TOPSWOPS CSECT

USING TOPSWOPS,R13 base register

BR R14 ---------------}-----------------------------------

YREGS

{{out}}

<pre>

This is a straightforward approach that counts the number of swaps for each permutation. To generate all permutations over 1 .. N, for each of N in 1 .. 10, the package Generic_Perm from the Permutations task is used [[http://rosettacode.org/wiki/Permutations#The_generic_package_Generic_Perm]].

 

 

procedure Topswaps is

Ada.Integer_Text_IO.Put(Item => Topswaps(I), Width => 3);

end loop;

 

{{out}}<pre> 0 1 2 4 7 10 16 22 30 38</pre>

 

=={{header|AutoHotkey}}==

R := []

for i, val in obj{

R[A_Index]:= A_LoopField

return R

Res := Print(Cards)

while (Cards[1]<>1)

Res .= (A_Index=1?"":"`t") val

return Trim(Res,"`n")

Outputs:<pre>2 4 1 3

4 2 1 3

=={{header|C}}==

An algorithm that doesn't go through all permutations, per Knuth tAoCP 7.2.1.2 exercise 107 (possible bad implementation on my part notwithstanding):

#include <string.h>

 

 

return 0;

The code contains critical small loops, which can be manually unrolled for those with OCD. POSIX thread support is useful if you got more than one CPUs.

#include <stdio.h>

#include <string.h>

return 0;

 

=={{header|C++}}==

#include <iostream>

#include <vector>

}

return 0;

 

{{out}}

http://rosettacode.org/wiki/Permutations#Faster_Lazy_Version

{{trans|Haskell}}

 

int topswops(in int n) pure @safe {

foreach (immutable i; 1 .. 11)

writeln(i, ": ", i.topswops);

{{out}}

<pre>1: 0

===D: Faster Version===

{{trans|C}}

 

__gshared uint[32] best;

foreach (immutable i; staticIota!(1, 14))

writefln("%2d: %d", i, topswops!i());

{{out}}

<pre> 1: 0

 

=={{header|Eiffel}}==

class

TOPSWOPS

 

end

Test:

class

APPLICATION

 

end

{{out}}

<pre>

=={{header|Elixir}}==

{{trans|Erlang}}

def get_1_first( [1 | _t] ), do: 0

def get_1_first( list ), do: 1 + get_1_first( swap(list) )

end

 

 

{{out}}

=={{header|Erlang}}==

This code is using the [[Permutations | permutation]] code by someone else. Thank you.

-module( topswops ).

 

 

get_1_first_many( N_permutations ) -> [get_1_first(X) || X <- N_permutations].

{{out}}

<pre>

 

=={{header|Factor}}==

math.ranges sequences ;

FROM: sequences.private => exchange-unsafe ;

10 [1,b] [ dup topswops "%2d: %2d\n" printf ] each ;

 

{{out}}

<pre>

 

=={{header|Fortran}}==

implicit none

contains

end do

end program

 

=={{header|Go}}==

// at Donald Knuth's web site. Algorithm credited there to Pepperdine

// and referenced to Mathematical Gazette 73 (1989), 131-133.

}

return m

{{out}}

<pre>

=={{header|Haskell}}==

====Searching permutations====

 

topswops :: Int -> Int

 

main =

{{out}}

<pre>1: 0

'''Alternate version'''

<br>Uses only permutations with all elements out of place.

import Control.Arrow (first)

 

 

main :: IO ()

'''Output'''

<pre>(1,0)

build the original list of 1..n values.

 

every n := 1 to 10 do {

ts := 0

if *A <= 1 then return A

suspend [(A[1]<->A[i := 1 to *A])] ||| permute(A[2:0])

 

Sample run:

 

=={{header|J}}==

2 4 1 3

4 2 1 3

3 1 2 4

2 1 3 4

1 0

2 1

8 22

9 30

'''Notes''': Readers less familiar with array-oriented programming may find [[Talk:Topswops#Alternate_J_solution|an alternate solution]] written in the structured programming style more accessible.

 

=={{header|Java}}==

{{trans|D}}

static final int maxBest = 32;

static int[] best;

System.out.println(i + ": " + topswops(i));

}

{{out}}

<pre>1: 0

 

'''Infrastructure:'''

def until(cond; next):

def _until:

else

. as $n | ($n-1) | permutations | [$n-1, .] | insert

'''Topswops:'''

def flips:

# state: [i, array]

def fannkuch:

reduce permutations as $p

 

'''Example:'''

{{out}}

[1,0]

[2,1]

[8,22]

[9,30]

 

=={{header|Julia}}==

Fast, efficient version

n == 1 && return 0

n == 2 && return 1

end

end

{{out}}

<pre>julia> function main()

=={{header|Kotlin}}==

{{trans|Java}}

 

val best = IntArray(32)

fun main(args: Array<String>) {

for (i in 1..10) println("${"%2d".format(i)} : ${topswops(i)}")

 

{{out}}

 

=={{header|Lua}}==

function permute (list)

local function perm (list, n)

-- Main procedure

{{out}}

<pre>1 0

10 38</pre>

 

An exhaustive search of all possible permutations is done

swaps[a_] := Length@FixedPointList[flip, a] - 2

{{out}}

2: 1

3: 2

=={{header|Nim}}==

{{trans|Java}}

 

const maxBest = 32

 

for i in 1..10:

{{out}}

<pre>

=={{header|PARI/GP}}==

Naive solution:

my(t=v[1]+1);

if (t==2, return(0));

mx;

}

{{out}}

<pre>%1 = [0, 1, 2, 4, 7, 10, 16, 22, 30, 38]</pre>

=={{header|Perl}}==

Recursive backtracking solution, starting with the final state and going backwards.

sub next_swop {

my( $max, $level, $p, $d ) = @_;

 

printf "Maximum swops for %2d cards: %2d\n", $_, topswops $_ for 1..10;

 

{{out}}

=={{header|Phix}}==

Originally contributed by Jason Gade as part of the Euphoria version of the Great Computer Language Shootout benchmarks.

{{out}}

<pre>

30

38

</pre>

 

=={{header|PicoLisp}}==

(let (Lst (range 1 N) L Lst Max)

(recur (L) # Permute

 

(for I 10

Output:

<pre>1 0

=={{header|PL/I}}==

{{incorrect|PL/I|Shown output is incorrect at the very least.}}

(subscriptrange):

topswap: procedure options (main); /* 12 November 2013 */

end;

end topswap;

<pre>

1: 1

 

=={{header|Potion}}==

i = 0, l = list(b-a+1)

while (a + i <= b):

if (n<1): n=10.

fannkuch(n)

 

Output follows that of Raku and Python, ~2.5x faster than perl5

=={{header|Python}}==

This solution uses cards numbered from 0..n-1 and variable p0 is introduced as a speed optimisation

>>> def f1(p):

i = 0

9 30

10 38

 

===Python: Faster Version===

{{trans|C}}

import psyco

psyco.full()

 

for i in xrange(1, 13):

{{out}}

<pre> 1: 0

=={{header|R}}==

Using iterpc package for optimization

topswops <- function(x){

i <- 0

result <- rbind(result, c(i, max(A$flips)))

}

 

Output:

Simple search, only "optimization" is to consider only all-misplaced permutations (as in the alternative Haskell solution), which shaves off around 2 seconds (from ~5).

 

#lang racket

 

 

(for ([i (in-range 1 11)]) (printf "~a\t~a\n" i (topswops i)))

 

Output:

=={{header|Raku}}==

(formerly Perl 6)

my int $count = 0;

until @a[0] == 1 {

sub topswops($n) { max (1..$n).permutations.race.map: &swops }

 

{{Out}}

<pre>1 0

Alternately, using string manipulation instead. Much faster, though honestly, still not very fast.

 

my int $count = 0;

while (my \l = $a.ord) > 1 {

sub topswops($n) { max (1..$n).permutations.map: { .chrs.join.&swops } }

 

 

Same output

The &nbsp; '''decks''' &nbsp; function is a modified permSets (permutation sets) subroutine,

<br>and is optimized somewhat to take advantage by eliminating one-swop "decks".

 

end /*i*/

say '──────── maximum swops for a deck of' right(n,2) ' cards is' right(mx,4)

end /*n*/

/*──────────────────────────────────────────────────────────────────────────────────────*/

decks: procedure expose !.; parse arg x,y,,$ @. /* X things taken Y at a time. */

return # /*return number of permutations (decks)*/

.decks: procedure expose !. @. x y $ #; parse arg ?

end

else if @.1==? then qs=2 /*skip the 1-swops: 3 x 1 x ···*/

else qs=1

end

return

/*──────────────────────────────────────────────────────────────────────────────────────*/

end /*h*/

{{out|output|text=&nbsp; when using the default input:}}

=={{header|Ruby}}==

{{trans|Python}}

i = 0

while (a0 = a[0]) > 1

for n in 1..10

puts "%2d : %d" % [n, fannkuch(n)]

 

{{out}}

'''Faster Version'''

{{trans|Java}}

@best[n] = d if d > @best[n]

(n-1).downto(0) do |i|

for i in 1..10

puts "%2d : %d" % [i, topswops(i)]

 

=={{header|Scala}}==

 

def fannkuchen(l: List[Int], n: Int, i: Int, acc: Int): Int = {

assert(result == Vector((1, 0), (2, 1), (3, 2), (4, 4), (5, 7), (6, 10), (7, 16), (8, 22), (9, 30), (10, 38)), "Bad results")

println(s"Successfully completed without errors. [total ${scala.compat.Platform.currentTime - executionStart} ms]")

Computing results...

Pfannkuchen(1) = 0

=={{header|Tcl}}==

{{tcllib|struct::list}}<!-- Note that struct::list 1.8.1 (and probably earlier too) has a bug which makes this code hang when computing topswops(10). -->Probably an integer overflow at n=10.

 

proc swap {listVar} {

}

}

n topswops(n)

1 0

{{trans|Go}}

{{libheader|Wren-fmt}}

 

var maxn = 10

}

 

 

{{out}}

 

=={{header|XPL0}}==

int N, Max, Card1(16), Card2(16);

 

IntOut(0, N); ChOut(0, ^ ); IntOut(0, Max); CrLf(0);

];

 

{{out}}

{{trans|C}}

 

int N, D, Best(16);

IntOut(0, N); Text(0, ": "); IntOut(0, Best(N)); CrLf(0);

];

 

{{out}}

{{trans|D}}

Slow version

flip:=fcn(xa){

if (not xa[0]) return(0);

}

 

{{out}}

<pre>