> -----Oorspronkelijk bericht-----
> Van: [EMAIL PROTECTED] [mailto:programming-
> [EMAIL PROTECTED] Namens Ralph G Selfridge
> Verzonden: maandag 27 augustus 2007 22:24
> Aan: [email protected]
> Onderwerp: [Jprogramming] Permutations of a sort.
>
> Here's my problem. I have a binary string, potentially long, in my case
> 28. I need to get all binary strings with a specified number of 1s. I
> doubt
> I can get them all at once, too many, so how do I get from one to the
> next?
>
> What next means is irrelvant, just so I get them with no duplicates if I
> run long emough.
>
> While I have an answer, I'm curious to see if there is a better way.
>
>
> Ralph S
>
> ----------------------------------------------------------------------
> For information about J forums see http://www.jsoftware.com/forums.htm
I think the best you can do is divide and conquer.
Suppose you want all weight 14 binary vectors of length 28, there are
40116600 = 14!18 of them, which result in an out of memory error.
But they can be processed by combining all binary vectors of length 14 and
weight at most 7. Which are 9908 = +/14!~i.8 only.
With
ncb=: [: |.@; [: (+&.> <@;\.)/ 2 <[EMAIL PROTECTED] [EMAIL PROTECTED] +/&i.
<:@-
the length 14 binary vectors of weight 1 to 7 are produced by
$&.>(>:i.7) <@#:@ncb"0 [14
+-----+-----+------+-------+-------+-------+-------+
|14 14|91 14|364 14|1001 14|2002 14|3003 14|3432 14|
+-----+-----+------+-------+-------+-------+-------+
Now the vectors of >:7 weight are the complements of these.
And combining vectors of length 14 and weight k = >:i.7 with those of length
14 and weight 14-k produces the desired ones.
cmbnvctrs=: 3 : 0 NB. combine vectors of (>:i.7) <@#:@ncb"0 [14
for_j. y do.
z=. (,"1"1 _-.)&> j NB. ($z)=(#,$)j
NB. process vectors of z
end.
)
Hope this helps.
It is at least faster than processing them one by one.
If this still results in an out of memory error, perhaps with the 3432
weight 7 vectors of length 14, than a division in smaller portions should be
appropriate.
BTW, for smaller weight vectors of length 28 we have
28(],.!~)i.15
0 1
1 28
2 378
3 3276
4 20475
5 98280
6 376740
7 1184040
8 3108105
9 6906900
10 13123110
11 21474180
12 30421755
13 37442160
14 40116600
I get an o.o.m.-error only at 10 #:@ncb 28 and at 13 ncb 28.
So until weight 10, all vectors can be generated in binary form. And for
weight 10, 11 and 12 the decimal values of these binary vectors can be
generated, after which they can be divided and processed separately.
R.E. Boss
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
