There is only one cycle, yes. The point of the example was to demonstrate
pathology with a very long cycle.
On Fri, 17 Mar 2023, Jan-Pieter Jacobs wrote:
Probably it's just something going over my head, but how do these
permutations have more than one cycle?
#@C. _1 1 |."0 _ i. 128
1 1
C.
Oh, nice! I tried <./{~^:(<2>.@^.#p)p, but that loses information; your
solution retains it in m.
On Thu, 16 Mar 2023, Marshall Lochbaum wrote:
Interesting problem! I think this works: for starting permutation p,
keep two lists. At step i,
- l is {~^:i p, that is, the index 2^i steps further
Probably it's just something going over my head, but how do these
permutations have more than one cycle?
#@C. _1 1 |."0 _ i. 128
1 1
C. y returns boxed cycles in permutation y.
What am I missing?
Jan-Pieter
On Fri, 17 Mar 2023, 01:07 Marshall Lochbaum, wrote:
> Interesting problem! I thin
Interesting problem! I think this works: for starting permutation p,
keep two lists. At step i,
- l is {~^:i p, that is, the index 2^i steps further along the cycle
- m is the minimum index among those less than 2^i steps ahead.
Initially l is p and m is i.#p . To update, simultaneously replace l
I can characterise the cycles of a permutation with (<.{~)^:_ (this keys each
cycle by its lowest element, but any unique key is fine).
But although this sometimes has log span (in the length of the longest cycle):
# (<.{~)^:(<_) _1|.i.128
8
The worst case is linear span:
# (<.{~)^:(<_)
A slight variation:
permh=: (- i.) #: i.@!
Thanks again,
--
Raul
On Sun, Oct 31, 2021 at 2:27 PM xash wrote:
>
> With mixed bases, for e.g. 3:
> 3 2 1 #: i. 6
>
> An equivalent function of permh is thus:
> (>:@i.@- #: i.@!) 3
>
> If you want to map arbitrary n to a permutation with unknown
Nice!
(I feel like I should have seen that...)
Thanks,
--
Raul
On Sun, Oct 31, 2021 at 2:27 PM xash wrote:
>
> With mixed bases, for e.g. 3:
> 3 2 1 #: i. 6
>
> An equivalent function of permh is thus:
> (>:@i.@- #: i.@!) 3
>
> If you want to map arbitrary n to a permutation with unknown leng
With mixed bases, for e.g. 3:
3 2 1 #: i. 6
An equivalent function of permh is thus:
(>:@i.@- #: i.@!) 3
If you want to map arbitrary n to a permutation with unknown length,
you could use something like this (I love J for things like !^:_1):
(#:~ [:>:@i.@-@<.@>: !^:_1)"0 (2+i.4) NB. needs specia
(I really do not know the "right" historical terminology for talking
about this, thus the subject line and the odd intro I am using here.)
In the Tower of Hanoi puzzle, we move a stack of disks from one tower
to another, moving only the top piece.
But imagine that we could remove the disks in any
Hi,
thanks for all the input,
Jimmy
PS It seems the sequence 0 6 1 7 2 8 3 9 4 10 5 lost its last
element during the editing process (thanks to those who pointed it out).
On Wed, Jan 29, 2020 at 4:40 AM Jan-Pieter Jacobs <
janpieter.jac...@gmail.com> wrote:
> There's two pages in Fifty
There's two pages in Fifty shades of J that might be of interest too:
https://code.jsoftware.com/wiki/Fifty_Shades_of_J/Chapter_31
https://code.jsoftware.com/wiki/Fifty_Shades_of_J/Chapter_32
Jan-Pieter
On Wed, Jan 29, 2020, 06:20 Devon McCormick wrote:
> Has no one mentioned "A." yet?
>
> On
Has no one mentioned "A." yet?
On Tue, Jan 28, 2020 at 10:10 PM Henry Rich wrote:
> This is the Chinese Remainder Theorem, no?
>
> Henry Rich
>
> On 1/28/2020 9:49 PM, 'Jon Hough' via Programming wrote:
> > See Modulo Multiplication Group:
> > https://en.wikipedia.org/wiki/Multiplicative_group
I think the CRT is related (
https://en.wikipedia.org/wiki/Chinese_remainder_theorem ) in the sense that it
is about modulo arithmetic and congruences, but I am not sure it has much to do
with permutations fo the moduli. It states that given some pairwise coprime x1
x2 x3 ... xk, then
if N =
This is the Chinese Remainder Theorem, no?
Henry Rich
On 1/28/2020 9:49 PM, 'Jon Hough' via Programming wrote:
See Modulo Multiplication Group:
https://en.wikipedia.org/wiki/Multiplicative_group_of_integers_modulo_n
http://mathworld.wolfram.com/ModuloMultiplicationGroup.html
Since 11 is pri
See Modulo Multiplication Group:
https://en.wikipedia.org/wiki/Multiplicative_group_of_integers_modulo_n
http://mathworld.wolfram.com/ModuloMultiplicationGroup.html
Since 11 is prime, its modulo multiplication group has 10 elements (all the
numbers from 1 to 10). i.e. multiplying the elements b
This is a beautiful list! Thank you for sharing.
Regarding your 3) and 6) versions with modulo arithmetic, happily, this is a
standard result from number theory. You should be able to find the relevant
background and theorem itself near the beginning of any introductory Number
Theory book. IIRC, m
Hi,
I am looking for some reference texts on permutations and modular
arithmetic.
I recently stumbled on some interesting properties of card shuffles.
For example, using a deck of 11 cards labeled 0 through 10 and shuffling
them to obtain this layout :
0 6 1 7 2 8 3 9 4 10
There are
ent: Monday, May 2, 2016 2:47 PM
Subject: Re: [Jprogramming] permutations the slow way
This, perhaps:
;"1 ({.,"0 1 $:^:(1(] <@; $:^:(1 < #)@-.)"1 0~ 0 1 2 3
Sorry about the goof, earlier.
Thanks,
--
Raul
On Mon, May 2, 2016 at 2:40 PM, Raul Miller wrote:
> Thi
;"1)@:((] ,"0 1 $:^:(1 < #)@-.)"1 0~) 0 1 2 3
>>
>> but I also struggle with the tree walking approach that is say generated with
>>
>> (] <@; $:^:(1 < #)@-.)"1 0~ 0 1 2 3
>>
>>
>>
>> - Original Message -
ree walking approach that is say generated with
>>
>> (] <@; $:^:(1 < #)@-.)"1 0~ 0 1 2 3
>>
>>
>>
>> - Original Message -
>> From: Raul Miller
>> To: Programming forum
>> Sent: Monday, May 2, 2016 1:06 PM
>> Su
gt;
> ,&.:(<"1)@:((] ,"0 1 $:^:(1 < #)@-.)"1 0~) 0 1 2 3
>
> but I also struggle with the tree walking approach that is say generated with
>
> (] <@; $:^:(1 < #)@-.)"1 0~ 0 1 2 3
>
>
>
> - Original Message -
> From: Rau
-- Original Message -
From: Raul Miller
To: Programming forum
Sent: Monday, May 2, 2016 1:06 PM
Subject: Re: [Jprogramming] permutations the slow way
This good enough?
;"1 ({.,.>@}.)S:2 (] <@; $:^:(1 < #)@-.)"1 0~ 0 1 2
Or did you have additional constraints?
Thank
This good enough?
;"1 ({.,.>@}.)S:2 (] <@; $:^:(1 < #)@-.)"1 0~ 0 1 2
Or did you have additional constraints?
Thanks,
--
Raul
On Mon, May 2, 2016 at 11:21 AM, 'Pascal Jasmin' via Programming
wrote:
> how might you derive the unboxed permutation list from this tree?
>
> (] <@; $:^:(1 < #)
how might you derive the unboxed permutation list from this tree?
(] <@; $:^:(1 < #)@-.)"1 0~ 0 1 2
+---+---+---+
|+-+-+-+|+-+-+-+|+-+-+-+|
||0|+-+-+|+-+-+|||1|+-+-+|+-+-+|||2|+-+-+|+-+-+||
|| ||1|2|||2|1 ||0|2|||2|0 ||0|1|||1|0
Nice, thank you.
- Original Message -
From: R.E. Boss
To: programm...@jsoftware.com
Cc:
Sent: Friday, August 21, 2015 2:45 PM
Subject: Re: [Jprogramming] permutations without reverses
ts'(#~({.<{:)"1)(i.@!A.i.)8'
0.029197332 9048960
R.E. Boss
>
ijdag 21 augustus 2015 19:36
> To: programm...@jsoftware.com
> Subject: Re: [Jprogramming] permutations without reverses
>
> A version that compares every element to the whole list (so far) to filter
out
> is innefficient even for perm 8
>
> reduce =: 1 : '<"_
om: 'Pascal Jasmin' via Programming
To: Programming Forum
Cc:
Sent: Friday, August 21, 2015 1:10 PM
Subject: [Jprogramming] permutations without reverses
for 3, removing the "reverse duplicates" of permutations is as easy as taking
the top half
(i.@! A. i.) 3
0 1 2
0 2 1
for 3, removing the "reverse duplicates" of permutations is as easy as taking
the top half
(i.@! A. i.) 3
0 1 2
0 2 1
1 0 2
1 2 0
2 0 1
2 1 0
last (5) is reverse of 0. 4 is reverse of 2, and 3 reverse of 1
Is there a function for producing permutations without their reverse included?
tware.com] On Behalf Of R.E. Boss
> Sent: zondag 26 april 2015 9:32
> To: programm...@jsoftware.com
> Subject: Re: [Jprogramming] Permutations with repeats (combinations?)
>
> comb=: 4 : 0
> k=. i.>:d=.y-x
> z=. (d$ for. i.x do. z=. k ,.&.> ,&.>/\.
]'
2 3+codeinsert 1 2 3
2+3+1 2 3
(2;3)+codeinsert 1 2 3
2+3+1 2 3
(2 1 4; 3)+codeinsert 1 2 3
2 1 4+3+1 2 3
It avoids the boxing, though I doubt its practical for lengthy data.
- Original Message -
From: Jose Mario Quintana
To: Programming foru
mp;.>)/)(>@:)
> reduce =: 1 : '<"_1@[ ([: u boxscan ,) <@:]'
>
>
> The list has brought this up before, but is a foreign to do this something
> easy and worthwhile?
>
>
>
> - Original Message -
> From: Jose Mario Quintana
> To: Progr
inal Message -
From: Jose Mario Quintana
To: Programming forum
Cc:
Sent: Monday, April 27, 2015 7:45 PM
Subject: Re: [Jprogramming] Permutations with repeats (combinations?)
Right, this is because "I did not make any effort to simplify or to try to
optimize the tacit verbs" The tool
d side of ^:
>
> combT =: ([: ; ([ ; [: i.@>: -~) ((1 {:: [) ,.&.> [: ,&.>/\.
> >:&.>@:])^:(0 {:: [) (
> 100 timespacex&> ' 2 combT 5' ; ' 2 combt 5'
> 1.91616e_5 5888
> 3.6608e_5 9088
>
>
> 100 timespacex&> '
0.0584915 5.03404e7
0.0580249 3.38226e7
- Original Message -
From: Jose Mario Quintana
To: Programming forum
Cc:
Sent: Sunday, April 26, 2015 9:55 PM
Subject: Re: [Jprogramming] Permutations with repeats (combinations?)
Tacit vs. explicit seems to be a never-ending controversy. May as
re equivalence, but
> there
> is a J
> > feature I have not seen before
> >
> >$ every ( [ ,"1"1 _1 ] {"1"_ 1 [ -.~"1 i.@(+&({:@$)))L:0/ |. (]
> <@comb"0 +/\)
> > |.#/.~ 1 1 2 3 3
> > 10 3 1 5
> >
> >
> >
...@forums.jsoftware.com] On Behalf Of 'Pascal Jasmin' via
> Programming
> Sent: zondag 26 april 2015 17:19
> To: programm...@jsoftware.com
> Subject: Re: [Jprogramming] Permutations with repeats (combinations?)
>
> Nice,
>
> I find this easy to follow as there is
(i. 3 2 2) +"1"2 i. 2 2
0 2
4 6
4 6
8 10
8 10
12 14
(i. 3 2 2) +"1 i. 2 2
|length error
| (i.3 2 2)+"1 i.2 2
Henry Rich
On 4/26/2015 11:19 AM, 'Pascal Jasmin' via Programming wrote:
I understand that v"1"2 -: v"1 in all cases?... but not necessarily v"1"_1
quot;1"_1
- Original Message -
From: R.E. Boss
To: programm...@jsoftware.com
Cc:
Sent: Sunday, April 26, 2015 3:31 AM
Subject: Re: [Jprogramming] Permutations with repeats (combinations?)
comb=: 4 : 0
k=. i.>:d=.y-x
z=. (d$ ,&.>/\. >:&.> z end.
; z
)
cmbcomb=:
6'
> 3.8703475 3.2212362e9
>
>
> R.E. Boss
>
> (Add your info to
> http://www.jsoftware.com/jwiki/Community/Demographics )
>
>
> > -Original Message-
> > From: programming-boun...@forums.jsoftware.com
> [mailto:programming-
>
5 10:49
> To: Programming forum
> Subject: Re: [Jprogramming] Permutations with repeats (combinations?)
>
> I cannot reproduce your result.
>
> I get this:
> comb=: 4 : 0
> k=. i.>:d=.y-x
> z=. (d$ for. i.x do. z=. k ,.&.> ,&.>/\. >:&.> z end.
>
mming-
>> boun...@forums.jsoftware.com] On Behalf Of Raul Miller
>> Sent: zondag 26 april 2015 3:22
>> To: Programming forum
>> Subject: Re: [Jprogramming] Permutations with repeats (combinations?)
>>
>> That's an error on my part.
>>
>> It' not
--Original Message-
> From: programming-boun...@forums.jsoftware.com [mailto:programming-
> boun...@forums.jsoftware.com] On Behalf Of R.E. Boss
> Sent: zondag 26 april 2015 8:59
> To: programm...@jsoftware.com
> Subject: Re: [Jprogramming] Permutations with repeats (combinations?)
&
Sent: zondag 26 april 2015 3:22
> To: Programming forum
> Subject: Re: [Jprogramming] Permutations with repeats (combinations?)
>
> That's an error on my part.
>
> It' not unique to boxed data, you can see the same flaw with:
>
> peermm 'ababc'
>
rm2 1 2 ; 1 2 ; 3 ;3 ; 3
>> 3 3 1 2 1 2 3
>> 3 3 1 2 3 1 2
>> 3 3 3 1 2 1 2
>> 3 1 2 3 1 2 3
>> 3 1 2 3 3 1 2
>> 3 1 2 1 2 3 3
>> 1 2 3 3 1 2 3
>> 1 2 3 3 3 1 2
>> 1 2 3 1 2 3 3
>> 1 2 1 2 3 3 3
>>
>>
>>
>>
>>
>>
>>
this has wrong results
peermm 1 1 ; 2 2 ; 1 1 ; 2 2 ;3
- Original Message -
From: Raul Miller
To: Programming forum
Cc:
Sent: Saturday, April 25, 2015 8:24 PM
Subject: Re: [Jprogramming] Permutations with repeats (combinations?)
What problem does it have with boxed data? (It worked
>
>
>
>
>
> - Original Message -
> From: Raul Miller
> To: Programming forum
> Cc:
> Sent: Saturday, April 25, 2015 2:02 PM
> Subject: Re: [Jprogramming] Permutations with repeats (combinations?)
>
> My first attempt at implementing like that ran into a problem
2 1 2 3 3 3
- Original Message -
From: Raul Miller
To: Programming forum
Cc:
Sent: Saturday, April 25, 2015 2:02 PM
Subject: Re: [Jprogramming] Permutations with repeats (combinations?)
My first attempt at implementing like that ran into a problem with
mix-matched types in r for
My first attempt at implementing like that ran into a problem with
mix-matched types in r for some cases, so I reworked the thing to
support arguments of any type:
comb=: 4 : 0
k=. i.>:d=.y-x
z=. (d$ ,&.>/\. >:&.> z end.
; z
)
peermm=:3 :0
arg=. (/: #@>) arg
m=. (i.@! A. i.)n1
for_d.n1}.
The peermm function can be made faster by doing the actual permutations of
those cells of wrote:
> On Fri, Apr 24, 2015 at 7:03 PM, Roger Hui
> wrote:
> > The details of implementing this algorithm are left as an exercise for
> the
> > reader. :-)
>
> Do I qualify as a reader?
>
> comb=: 4 : 0
>
xtras=. ; }. each
To: Programming forum
Cc:
Sent: Saturday, April 25, 2015 1:46 AM
Subject: Re: [Jprogramming] Permutations with repeats (combinations?)
On Fri, Apr 24, 2015 at 7:03 PM, Roger Hui wrote:
> The details of implementing this algorithm are left as an exercise for the
> reader.
V. good.
On Fri, Apr 24, 2015 at 10:46 PM, Raul Miller wrote:
> On Fri, Apr 24, 2015 at 7:03 PM, Roger Hui
> wrote:
> > The details of implementing this algorithm are left as an exercise for
> the
> > reader. :-)
>
> Do I qualify as a reader?
>
> comb=: 4 : 0
> k=. i.>:d=.y-x
> z=. (d$ for
On Fri, Apr 24, 2015 at 7:03 PM, Roger Hui wrote:
> The details of implementing this algorithm are left as an exercise for the
> reader. :-)
Do I qualify as a reader?
comb=: 4 : 0
k=. i.>:d=.y-x
z=. (d$ ,&.>/\. >:&.> z end.
; z
)
peermm=:3 :0
r=.i.1 0
for_d.d
n=.i.(#s)+{:$r
e=.n
Here's a recursive implementation.
tree =: ({.,<@$:@;@}.)"1@(({.;}.)S:0,.1[\.])^:(0<#)@( wrote:
> archive or wiki did not help, but perhaps I searched wrong
>
> perm =: i.@! A. i.
>
> ~.@({~ [: perm #) 1 1 2 2
> 1 1 2 2
> 1 2 1 2
> 1 2 2 1
> 2 1 1 2
> 2 1 2 1
> 2 2 1 1
>
> while that is the ans
end.
p =. ~. o end.
)
- Original Message -
From: 'Pascal Jasmin' via Programming
To: "programm...@jsoftware.com"
Cc:
Sent: Friday, April 24, 2015 7:54 PM
Subject: Re: [Jprogramming] Permutations with repeats (combinations?)
I haven't quite used all of these
2 2 7 7 8 8 9 9 9 9 9 9 '
0.54311 9.28059e7
- Original Message -
From: Roger Hui
To: Programming forum
Cc:
Sent: Friday, April 24, 2015 7:03 PM
Subject: Re: [Jprogramming] Permutations with repeats (combinations?)
The "secret" is to avoid generating duplicates which are t
The "secret" is to avoid generating duplicates which are then removed.
Partition the argument into a collection of like elements:
:d=.y-x
z=. (d$ ,&.>/\. >:&.> z end.
; z
)
(#s) comb (#s)+{:$m
0 1
0 2
0 3
1 2
1 3
2 3
From these column indices generate the z:
0 1 2 2 0 1
2 2 1 0
0
My take:
d=: 1 1 2 2
f=: ~.@: (] {~ (i.@! A. i.)@#)
f d
1 1 2 2
1 2 1 2
1 2 2 1
2 1 1 2
2 1 2 1
2 2 1 1
On Fri, Apr 24, 2015 at 4:00 PM, 'Pascal Jasmin' via Programming <
programm...@jsoftware.com> wrote:
> archive or wiki did not help, but perhaps I searched wrong
>
> perm =: i.@! A
archive or wiki did not help, but perhaps I searched wrong
perm =: i.@! A. i.
~.@({~ [: perm #) 1 1 2 2
1 1 2 2
1 2 1 2
1 2 2 1
2 1 1 2
2 1 2 1
2 2 1 1
while that is the answer I want, and is short and elegant, it grows very
innefficient as the length of the argument grows even if the
58 matches
Mail list logo
