I need to implement this
http://www.cut-the-knot.org/Curriculum/Combinatorics/JohnsonTrotter.shtml

But I'm already stuck with the data structure...

Why
data Versus = Versus 0 | Versus 1 or
data Versus = 0 | 1

are wrong?
I need a list with a direction for every element, I thought something
like

data Lista a = Lista [(a,Versus)]
does it make sense?

andrea wrote:

The format for a data declaration is:

data TypeName = Contstuctor1 Type11 Type12 ...
| Constructor2 Type21 Type22 ...
| ...

So 'data Versus = Versus 0 | Versus 1' is wrong for a couple reasons:

1) Both constructors are named the same thing, so there'd be no way to tell
which one you want on use.

2) 0 and 1 aren't the names of types, they're the names of numeric values.

In 'data Versus = 0 | 1', the error is that 0 and 1 are not available for
constructor names, already being numeric values.

What you want is something like:

data Versus = Up | Down

On 19 Set, 22:10, Dan Doel gmail.com> wrote:

andrea wrote:

Well, I suspect that a list isn't the best possible data structure for this
algorithm, but that really depends on what you want to do.

If you want to produce all permutations, then using lists might not be a bad
idea. However, if you want to, say, find the Nth permutation produced by
this algorithm, using a mutable array (IOArray or STArray) might save a lot
of allocation and be faster. It might also be easier to implement the
various operations in this algorithm with a mutable array (although doing
it with lists might force you to puzzle out some good ways of working on
them, and thus be a handy exercise anyway).

Note that due to Haskell's lazy evaluation, implementing the naive algorithm
described on that page isn't so bad. Yes, you must build a pyramid of all
smaller permutations, but such things are only built on demand. Consider
the following code:

Dan Doel wrote:

(Replying to myself...)

Here's an algorithm for finding a particular permutaton, the kth permutation
of size n:

insertAt 0 e l = e:l
insertAt n e [] = error "Index too large."
insertAt n e (x:xs) = x : insertAt (n-1) e xs

perm 0 _ = []
perm n k = insertAt m n (perm (n-1) d)
where (d,m) = k `divMod` n

It should match with the 'perms' function above via:

(perms n !! k) == perm n k

On 20 Set, 03:34, Dan Doel gmail.com> wrote:

andrea wrote:

A declaration starting with 'type' can be thought of like an alias. When you
have:

type IdxSet a = (Int, [a])

Effectively, the compiler replaces every 'IdxSet a' it sees with '(Int,
[a])' (it doesn't exactly do that, since it needs to keep track of what was
called 'IdxSet a' for the purpose of error messages, but that's a way of
understanding it).

data, however, creates a new type with its own constructors. So the closest
translation would be:

data IdxSet a = IS (Int, [a])

On 20 Set, 21:43, Dan Doel gmail.com> wrote:

andrea wrote:

Yes, that's right. The fact that it is so limited allows the compiler to
optimize things in ways that wouldn't hold for general data declarations,
but as far as how it works, it's about the same as a data declaration with
one constructor and one argument.

On 21 Set, 09:52, Dan Doel gmail.com> wrote:

Ok thanks, another little question about types... I have this
data Seme = Cuori | Quadri | Fiori | Piove deriving Show
data Range = Zero | Uno | Due | Tre deriving Show
data Carta = Carta Range Seme
How can I build a set with every possible cards automatically?
Is it impossibile in this way?