I agree Groeneveld's solution is elegant and it's certainly more efficient
for larger problems, My approach was the result of a couple of minutes
thought;
it turned out to be quite adequate for Skip's original requirement.
Consider the count of such n-digit numbers,
nq =: ! * !&9
nq 1 2 3 4 5 6 7 8 9 10
9 72 504 3024 15120 60480 181440 362880 362880 0
whereas the count of n-digit numbers is
nn =: 9 * 10&^@<:
so
(nq%nn) 1 2 3 4 5 6 7 8 9 10
1 0.8 0.56 0.336 0.168 0.0672 0.02016 0.004032 0.0004032 0
is the proportion of n-digit numbers that pass the check for
validity in my brute-force approach. (There are of course no valid
numbers with 10 or more digits!)
I believe Miller and Groeneveld's methods are essentially the same,
so should share similar performance. For three digits, the brute-force
competes well, but less and less well as the above ratio decreases.
Cheers,
Mike
On 15/08/2017 14:53, R.E. Boss wrote:
I suggest you use larger numbers for your performance tests.
(10#.(#~(-:~.)"1) >: 9#.inv i. 9^6)-: 10 #.(,/@:(],"1 0 -."1)^:5 ,.)>:i.9
1
ts'10#.(#~(-:~.)"1) >: 9#.inv i. 9^6'
0.39192919 1.7905766e8
ts'10 #.(,/@:(],"1 0 -."1)^:5 ,.)>:i.9'
0.010126433 9442816
The Groeneveld solution is more efficient by a factor of approx. 700 (38 * 19).
Apart from being the most elegant.
R.E. Boss
-----Original Message-----
From: Programming [mailto:[email protected]]
On Behalf Of 'Mike Day' via Programming
Sent: maandag 14 augustus 2017 22:01
To: [email protected]
Subject: Re: [Jprogramming] Quora problem
Yes, much better!
cf my suggestion a few days ago, and another constructive one using tap and
comb, q_tap_comb :
... time & space for Skip's original problem:
ts'10 #.(,/@:(],"1 0 -."1)^:2 ,.)>:i.9'NB. AG
0.000120949 40448
ts'10#.(#~(-:~.)"1) >: 9#.inv i. 9^3' NB. MD
0.000774292 84608
ts'q_tap_comb 3' NB. constructive, eg RM
0.00130777 39424
... generating required numbers in [12345, 98765]:
ts'10 #.(,/@:(],"1 0 -."1)^:4 ,.)>:i.9'
0.00548052 2.23386e6
ts'10#.(#~(-:~.)"1) >: 9#.inv i. 9^5'
0.066979 5.91731e6
ts'q_tap_comb 5'
0.0397513 2.11584e6
where
q_tap_comb =: tap @[ ,@(10 #."1 {&.:|:) >:@comb&9 f.
ie
q_tap_comb
(i.@! A. i.)@[ ,@(10 #."1 {&.:|:) >:@(4 : 0)&9
k=. i.>:d=.y-x
z=. (d$<i.0 0),<i.1 0
for. i.x do. z=. k ,.&.> ,&.>/\. >:&.> z end.
; z
)
Thanks,
Mike
On 14/08/2017 18:16, Arie Groeneveld wrote:
My version of variations (without repetitions) :
10 #. (,/@:(],"1 0 -."1)^:2 ,.)1+i.9
More general:
(3) 4 :'y,/@:(],"1 0 -."1)^:(x-1) ,.y' 'abcd'
Op 12-08-17 om 11:16 schreef Skip Cave:
How can I use J to generate all the possible 3-digit integers that
can be constructed using the digits 1-9 (no zeros), with no repeated
digits in each integer? The sequence starts with 123 (smallest) and
goes to 987 (largest). Here's the first few integers in the sequence:
123 124 125 126 127 128 129 132 134 135 136 137 138 139 142 143 145
146 147
148 149 152 153 154 156 157 158 159 162......
Skip
Skip Cave
Cave Consulting LLC
---------------------------------------------------------------------
- For information about J forums see
http://www.jsoftware.com/forums.htm
----------------------------------------------------------------------
For information about J forums see
http://www.jsoftware.com/forums.htm
---
This email has been checked for viruses by Avast antivirus software.
https://www.avast.com/antivirus
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
