Generating a permutation of a given list
Viru Honnur
I would like to know are there any Tcl libraries available to produce a
permutation of a given list, if not, could you suggest a way to write
one?.
For e.g. list 'A' {a b c}
can be permuted:
{a b c}
{a c b}
{b c a}
{b a c}
{c b a}
{c a b}
Thanks,
-Viru
Darren New
> I would like to know are there any Tcl libraries available to produce a
> permutation of a given list, if not, could you suggest a way to write
> one?.
Easy.
Note that a permutation of a 4-element list is the fourth element inserted
at each possible place in the permutations of a 3-element list, and that the
permutations of a 1-element list is just that list. The recursive solution
is fairly straightforward from that. (A one-liner in APL, for which I once
won a beer by getting it right on the first try. :-)
--
Darren New
San Diego, CA, USA (PST). Cryptokeys on demand.
** http://home.san.rr.com/dnew/DNResume.html **
** http://images.fbrtech.com/dnew/ **
My brain needs a "back" button so I can
remember where I left my coffee mug.
Neil Madden
>
> Viru Honnur wrote:
> > I would like to know are there any Tcl libraries available to produce a
> > permutation of a given list, if not, could you suggest a way to write
> > one?.
>
> Easy.
>
> Note that a permutation of a 4-element list is the fourth element inserted
> at each possible place in the permutations of a 3-element list, and that the
> permutations of a 1-element list is just that list. The recursive solution
> is fairly straightforward from that. (A one-liner in APL, for which I once
> won a beer by getting it right on the first try. :-)
>
proc permutations {list} {
if {[llength $list] == 1} {
return $list
}
set ret [list]
set pitem [lindex $list end]
set rest [permutations [lrange $list 0 end-1]]
# Right now insert our item at every position in the list
foreach item $rest {
for {set i 0} {$i < [llength $item]} {incr i} {
lappend ret [linsert $item $i $pitem]
}
lappend ret [concat $item $pitem]
}
return [lsort $ret]
}
Is there a more compact way of doing this in Tcl? How does the one-liner in APL
look? This algorithm is also seriously ugly in terms of time complexity. Doing
just [permutations {a b c d e f g h}] completely hangs wish on my machine.
--
package r Tkhtml;package r http;pack [scrollbar .v -o v -co {.h yv}] -s right\
-f y;pack [html .h -ys {.v set}] -f both -e 1;bind .h.x <1> {eval g [.h href %x\
%y]};proc g u {set t [http::geturl $u];.h cl;.h p [http::data $t];http::cleanup\
$t;.h co -base $u};g http://mini.net/tcl/976.html;proc bgerror args {};# NEM :-)
Darren New
> How does the one-liner in APL look?
Oh, like I could answer that in ASCII? ;-)
Seriously, it was a loooong time ago. A long long time ago. Back when I was
fighting in the clone wars.
> This algorithm is also seriously ugly in terms of time complexity.
I'm not sure why you're sorting at each step, but yes, it's a pretty
inefficient algorithm. Altho permutations are a pretty inefficient result -
I mean you get N! results anyway, don't you? No good way to make it faster
than N! if so.
There's also a way to do it based on Grey Codes, but I am not sure I
remember just what that is.
Andreas Kupries
Viru Honnur <viru...@cisco.com> writes:
> Hello,
>
> I would like to know are there any Tcl libraries available to produce a
> permutation of a given list, if not, could you suggest a way to write
> one?.
Start here
http://mini.net/tcl/2553.html
Not exactly what you want, but can give you some ideas.
--
Sincerely,
Andreas Kupries <akup...@shaw.ca>
Join us in Sept. for Tcl'2002: http://www.tcl.tk/community/tcl2002/
Developer @ <http://www.activestate.com/>
Private <http://www.purl.org/NET/akupries/>
-------------------------------------------------------------------------------
}
Richard Laing
Regards,
"Darren New" <dn...@san.rr.com> wrote in message
news:3CF815C5...@san.rr.com...
Neil Madden
>
> Neil Madden wrote:
> > How does the one-liner in APL look?
>
> Oh, like I could answer that in ASCII? ;-)
>
> Seriously, it was a loooong time ago. A long long time ago. Back when I was
> fighting in the clone wars.
>
> > This algorithm is also seriously ugly in terms of time complexity.
>
> I'm not sure why you're sorting at each step,
Oops - I just put that in at end to prettify the result, but didn't think that
it would then be sorting at every step :-) It was a bit late.
> but yes, it's a pretty
> inefficient algorithm. Altho permutations are a pretty inefficient result -
> I mean you get N! results anyway, don't you? No good way to make it faster
> than N! if so.
>
> There's also a way to do it based on Grey Codes, but I am not sure I
> remember just what that is.
>
--
lvi...@yahoo.com
According to Viru Honnur <viru...@cisco.com>:
:I would like to know are there any Tcl libraries available to produce a
:permutation of a given list, if not, could you suggest a way to write
:one?.
Take a look at <URL: http://purl.org/tcl/wiki/> - do a search for
permut - like this:
<URL: http://purl.org/tcl/wiki/permut* >
--
Support Internet Radio <URL: http://saveinternetradio.org/ >
Join Tcl'2002 in Vancouver http://www.tcl.tk/community/tcl2002/
Even if explicitly stated to the contrary, nothing in this posting
should be construed as representing my employer's opinions.
Kevin Kenny
>
> Hello,
>
> I would like to know are there any Tcl libraries available to produce a
> permutation of a given list, if not, could you suggest a way to write
> one?.
>
> For e.g. list 'A' {a b c}
Check the Wiki:
Scroll down to the item headed "Permute a list" near the bottom of the page.
--
73 de ke9tv/2, Kevin KENNY GE Corporate R&D, Niskayuna, New York, USA
Arjen Markus
>
> Darren New wrote:
> >
> > Viru Honnur wrote:
> > > I would like to know are there any Tcl libraries available to produce a
> > > permutation of a given list, if not, could you suggest a way to write
> > > one?.
> >
> > Easy.
> >
>
> Is there a more compact way of doing this in Tcl? How does the one-liner in APL
> look? This algorithm is also seriously ugly in terms of time complexity. Doing
> just [permutations {a b c d e f g h}] completely hangs wish on my machine.
>
On the Wiki you will find various solutions to problems of this
kind. Getting the power set of a list was solved by Kevin Kenny:
<http://wiki.tcl.tk/2827.html>
And there are numerous other pages to look for related items.
Regards,
Arjen
Cameron Laird
>Neil Madden wrote:
>> How does the one-liner in APL look?
>
>Oh, like I could answer that in ASCII? ;-)
.
.
Richard can: <URL: http://wiki.tcl.tk/1159.html >.
--
Cameron Laird <Cam...@Lairds.com>
Business: http://www.Phaseit.net
Personal: http://starbase.neosoft.com/~claird/home.html
Bob Techentin
> Darren New <dn...@san.rr.com> wrote:
> >Neil Madden wrote:
> >> How does the one-liner in APL look?
> >
> >Oh, like I could answer that in ASCII? ;-)
> .
But that's not just ASCII. That's TCL!!
(And besides, Richard can do a lot of things that take the rest of us
a little effort.)
Bob (gunning for QOTW)
--
Bob Techentin techenti...@mayo.edu
Mayo Foundation (507) 538-5495
200 First St. SW FAX (507) 284-9171
Rochester MN, 55901 USA http://www.mayo.edu/sppdg/
"
lvi...@yahoo.com
According to Arjen Markus <Arjen....@wldelft.nl>:
:> > Viru Honnur wrote:
:> > > I would like to know are there any Tcl libraries available to produce a
:> > > permutation of a given list, if not, could you suggest a way to write
:> > > one?.
:And there are numerous other pages to look for related items.
Alas, no one has taken on the Herculean task of turning all these wonderful
solutions into modules or procs in http://tcllib.sf.net/ so that they
are already available for the programmer...
Richard.Suchenwirth
>
> According to Arjen Markus <Arjen....@wldelft.nl>:
> :> > Viru Honnur wrote:
> :> > > I would like to know are there any Tcl libraries available to produce a
> :> > > permutation of a given list, if not, could you suggest a way to write
> :> > > one?.
>
> :And there are numerous other pages to look for related items.
>
> Alas, no one has taken on the Herculean task of turning all these wonderful
> solutions into modules or procs in http://tcllib.sf.net/ so that they
> are already available for the programmer...
Well, we are no Herculeses, but when I have a nifty, supposedly
generally useful proc (which fits between thumb and index finger) I put
it on one of these Wiki pages:
"Additional string/list/math/file functions"
- get the whole set from http://mini.net/tcl/additional
--
Schoene Gruesse/best regards, Richard Suchenwirth - +49-7531-86 2703
Siemens Dematic AG, PA RC D2, Buecklestr.1-5, 78467 Konstanz,Germany
Personal opinions expressed only unless explicitly stated otherwise.
Arjen Markus
> Alas, no one has taken on the Herculean task of turning all these wonderful
> solutions into modules or procs in http://tcllib.sf.net/ so that they
> are already available for the programmer...
>
Hm, perhaps we ought to invent some Ulyssean tricks, like:
Putting just a few nifty Richardian procs into a small module
and shift that into Tcllib.
Just the odd two (oops, make that three, otherwise we remain even :-),
to make a start. Then documentation remains a manageable task.
I like the idea, though ... It is too late for version 1.3, but,
that should not keep us from starting this.
Regards,
Arjen
Richard.Suchenwirth
> (And besides, Richard can do a lot of things that take the rest of us
> a little effort.)
>
> Bob (gunning for QOTW)
OK, now you got it (though I'm not so happy about it). It's not that I'm
a magician with a few extra spells that you others don't have. And the
things that I make public (and even more things I do at work, which are
company proprietary) often take me more than a little effort.
It's just that I (and we all) have this wonderful language named Tcl. I
am learning it since 1995, and am still learning new things. The typical
pattern is: I start with thinking "Wonder if that is possible too", do
some experiments, and very soon come to the conclusion: "But of course
it's possible!"
What helps in creative and productive Tcl coding, are in my opinion two
things:
(1) Be able to think like the parser. Read man Tcl(n) more than once,
think about each single word there. When you can anticipate what the
parser thinks when he sees your script, you can ride him like a
well-bred horse. And fly high.
(2) Step over thinking borders. Most of us have come from other
languages, and somehow incorporated categories of thinking imposed by
Fortran, C, what have you. These things are not laws of nature. A string
or array need not be dimensioned beforehand. To repeat Todd Coram's
golden words:
"Data typing is an illusion. Everything is a sequence of bytes. Call 'em
ints, floats, symbols, strings, whatever. Tcl exposes both code and data
to the user as sequences of bytes (called strings). This is Tcl's choice
of abstraction. And its quite a powerful choice IMHO."
http://mini.net/tcl/3018.html
Quick example for "string think": how to multiply an integer by
thousand:
append istring 000
(3) Don't be afraid of anything. Whatever the task, when you can
represent it with the functionality "one or more strings in, one string
out", chances are very good that you can implement it in Tcl. With a
little effort, of course, but very often with much less effort than in C
or Java.
Arjen Markus
>
>
> (2) Step over thinking borders. Most of us have come from other
> languages, and somehow incorporated categories of thinking imposed by
> Fortran, C, what have you. These things are not laws of nature. A string
> or array need not be dimensioned beforehand.
One thing I had to learn after years of programming in Fortran and
C is that there is no need to declare your variables at the start
of your procedure. You can do that locally:
foreach v $names {
global $v
upvar $v w
set w "A new value"
}
Or that procs can be defined in other procs:
proc aha { name } {
proc $name {puts "Hello, wonderful Tcl-world!" }
}
And the most surprising feature of Tcl (well, apart from being
able to redefine just about everything): data can be treated
as commands. Especially useful with configuration files and
such.
All these techniques are so much different from classical
programming languages (which do have the odd few things that
Tcl does not have, like, hm, ... - okay, I will think about
what things some more :-) that you really need to jump over
a few conceptual hurdles. And it is a pleasure to get assistence
from others!
Regards,
Arjen
Richard.Suchenwirth
> All these techniques are so much different from classical
> programming languages (which do have the odd few things that
> Tcl does not have, like, hm, ...
But what I'm having trouble with, trying to reproduce in Tcl, is block
structure
(like procs in procs, but which implicitly share elements of the
surrounding blocks) and lexical scoping (in Tcl we have two levels of
scope: global, possibly subdivided by namespaces, and local).
This seems to have been a progress introduced with Algol 60, and brought
over to Lisp, Pascal, C... But is it worth (and possible) to incorporate
in Tcl, other than with explicit tricks like additional parameters,
added via defaults or aliases? That of course works, but somehow feels
clumsy.
Bob Techentin
wrote:
> Bob Techentin wrote:
> > (And besides, Richard can do a lot of things that take the rest of
us
> > a little effort.)
> >
> > Bob (gunning for QOTW)
>
> OK, now you got it (though I'm not so happy about it). It's not that
I'm
> a magician with a few extra spells that you others don't have. And
the
> things that I make public (and even more things I do at work, which
are
> company proprietary) often take me more than a little effort.
Granted that it's not magic, and it is real work. But you really are
prolific, Richard. And you consistently share your efforts with the
community. For that you should be commended, and I thank you.
Bob