Return Styles: Pseud0ch, Terminal, Valhalla, NES, Geocities, Blue Moon.

Pages: 1-

[delphi] generating binary strings

Name: Anonymous 2012-01-19 18:10

How can I generate all binary strings of n length with m ones? (in delphi)
sample: n=3 m=2:
110
101
011

Name: Anonymous 2012-01-19 18:42

idiot way:
generate all strings with length n
check number of ones in all strings
discard those where m is not two

Name: Anonymous 2012-01-19 20:44

n=4 / m=2

O = 4 * 3 / 2 ??

------

n=5 / m=2

O = 5 * 4 / 2 ??

# #### (4+)/ X# ### (3+) / XX# ## (2+) / XXX# # (1 = 10)

Name: Anonymous 2012-01-19 20:48

APL way (M=8 and N=10):
((M←8)=+/A)⌿A←⍉(N/2)⊤⍳2*N←10

Name: Anonymous 2012-01-19 20:52

tricky-(ish) one

n=6 / m=3

O = 6 * 5 * 4 / (3 * 2 * 1)

Name: Anonymous 2012-01-19 20:56

super-tricky one ^^ (not really)

n = 5 / m= 3 (inverse of n=5 m=2)

5 * 4 * 3 / (3 * 2 * 1)

Name: Anonymous 2012-01-19 20:59

not really generating the strings though, just counting how many there should be =)

Name: Anonymous 2012-01-19 20:59

>>6
      ((M←3)=+/A)⌿A←⍉(N/2)⊤⍳2*N←5
0 0 1 1 1
0 1 0 1 1
0 1 1 0 1
0 1 1 1 0
1 0 0 1 1
1 0 1 0 1
1 0 1 1 0
1 1 0 0 1
1 1 0 1 0
1 1 1 0 0

Name: Anonymous 2012-01-19 21:36

>>8 what is that notation?

Name: Anonymous 2012-01-19 21:38

>>9
APL

Name: Anonymous 2012-01-19 21:55

eleventh hour dubs? (ala omega symbolism) ^^

Here's a challenge, calculate this for a trinary / [optional X-nary (uber-prog-challenge x) ] system ?

Name: Anonymous 2012-01-19 22:11

>>11
Here, X is the base, but it only finds the strings with M non-zero digits. It could be made more complicated to allow the number of each kind of digit to be selected.
      ((M←1)=+/0≠A)⌿A←⍉(N/X)⊤⍳(X←3)*N←3
0 0 1
0 0 2
0 1 0
0 2 0
1 0 0
2 0 0

Name: Anonymous 2012-01-19 22:11

... is it just (the above) multiplied by (base - 1) to the power of (n - m) ?

lol too easy?? =(

11:11 AM whoa

Name: Anonymous 2012-01-19 22:24

>>Proof enough?

110
101
011

112
121
211

Name: Anonymous 2012-01-19 22:34

>>13
((M←1)=+/0≠A)⌿A←⍉(N/X)⊤⍳(X←3)*N←3
1. Store 3 into N (number).
2. Store 3 into X (base).
3. Raise X to the Nth power (call this ⍵).
4. Create a vector from 0 to ⍵.
5. Duplicate X into an N-length vector (call this ⍺).
6. Convert each number in ⍵ into a base X number using ⍺ (call this ⍵).
7. Transpose matrix ⍵ and store it into A.
8. Store 1 into M.
9. Set a 0 for all 0 digits or a 1 for all non-zero digits in A.
10. Sum this to create a vector (call this ⍵).
11. Place a 1 if the element of ⍵ is equal to M or 0 otherwise (call this ⍺).
12. Select (gather) on the first axis all elements in A for which the corresponding element of ⍺ is 1 (the result).

Name: Anonymous 2012-01-19 22:45

>>12

n = 7, m1 = 2, m2 = 3, X = 4
[length 7, digit 1 occurs twice, d 2 occurs trice ^^, base 4]

uses (base - m [free-bases]) ^ (n - m1 - m2) [free length]

[(7 * 6 * 5 * 4 * 3) / [(2 * 1) * (3 * 2 * 1)]] * 2 ^ 2

= 840 ?

Name: Anonymous 2012-01-20 2:48

Gonna need that solution in Symta, with comments.

Name: op 2012-01-20 8:10

I still have no idea how to do it. Can someone write it in delphi/pascal?

Name: Anonymous 2012-01-20 9:09

ghci> nub $ permutations "110"
["110","011","101"]

Name: op 2012-01-20 9:24

>>18
it doesn't help.

Name: Anonymous 2012-01-20 10:39

>>20
SHUT THE FUCK UP

GO AWAY!!!!

Name: Anonymous 2012-01-20 11:31

>>21
4/10

Name: Anonymous 2012-01-20 16:36

>>22
nice dubs bro

Name: Anonymous 2012-01-20 16:41

3. Raise X to the Nth power (call this ⍵).
Where is the ⍵ in the code? Implicit?

Name: Anonymous 2012-01-20 16:51

>>24
In APL, ⍵ is usually used for the right argument of a function and ⍺ is usually used for the left argument.

Name: Anonymous 2012-01-20 18:15

Slow as fuck J solution:

   bins =: dyad : '~.(i.!x)A.(i.x)<y'
   7 bins 2
1 1 0 0 0 0 0
1 0 1 0 0 0 0
1 0 0 1 0 0 0
1 0 0 0 1 0 0
1 0 0 0 0 1 0
1 0 0 0 0 0 1
0 1 1 0 0 0 0
0 1 0 1 0 0 0
0 1 0 0 1 0 0
0 1 0 0 0 1 0
0 1 0 0 0 0 1
0 0 1 1 0 0 0
0 0 1 0 1 0 0
0 0 1 0 0 1 0
0 0 1 0 0 0 1
0 0 0 1 1 0 0
0 0 0 1 0 1 0
0 0 0 1 0 0 1
0 0 0 0 1 1 0
0 0 0 0 1 0 1
0 0 0 0 0 1 1

Name: >>26 2012-01-20 18:20

This just generates all permutations of a vector then takes the nub of that.

(i.x)           0 1 2 3 ... x-1
(i.x)<y         1 1 ... 1 (y times) 0 0 ... 0 (x times)
(i.!x)          0 1 2 3 ... fact(x)-1
a A. b          a'th permutation of b
~. a            nub of elements

Name: Anonymous 2012-01-20 22:47

>>1
Its a basic constraint problem, readily solved with recursion. You should do your own homework, so I'll give you pascal code run through Google Translate.

プログラムBinShit;
（* U MENA PASKAL*）
手順nbin（N、M：整数、tは文字列）;
開始
  もしN> 0
  開始
    もしM>0の場合、nbin（N - 1、M - 1、'1'+ t）は;
                  nbin（N - 1、M、'0'+ t）は
  最後に
  他
    の場合はm =0の場合、writelnの（T）
終わり;

開始
    nbin（3,2,'');
    readln
終わり。

Name: Anonymous 2012-01-20 23:42

three lines in prolog, yah!

GNU Prolog 1.3.0
By Daniel Diaz
Copyright (C) 1999-2007 Daniel Diaz
| ?- [user].
compiling user for byte code...
f(0,[]).
f(N,[0|R]) :- f(N,R).
f(N,[1|R]) :- NN is N - 1, f(NN,R).

user compiled, 4 lines read - 704 bytes written, 48521 ms

yes
| ?- f(2, [A,B,C,D,E]).

A = 0
B = 0
C = 0
D = 1
E = 1 ? ;

A = 0
B = 0
C = 1
D = 0
E = 1 ? ;

A = 0
B = 0
C = 1
D = 1
E = 0 ? ;

A = 0
B = 1
C = 0
D = 0
E = 1 ? ;

A = 0
B = 1
C = 0
D = 1
E = 0 ? ;

A = 0
B = 1
C = 1
D = 0
E = 0 ? ;

A = 1
B = 0
C = 0
D = 0
E = 1 ? ;

A = 1
B = 0
C = 0
D = 1
E = 0 ? ;

A = 1
B = 0
C = 1
D = 0
E = 0 ? ;

A = 1
B = 1
C = 0
D = 0
E = 0 ? ;

no

Name: Anonymous 2012-01-21 4:25

>>27

that's pretty impressive, considering the number of characters used to express it.

Name: Anonymous 2012-01-21 6:19

>>30
The A. operator did almost all the work for me. I'd say that other guy's APL implementations is at least a bit more impressive. The Prolog one is cool, too.
Don't change these.
Name: Email:
Entire Thread Thread List
All trademarks and copyrights on this site are owned by their respective parties. All comments and posts are the responsibility of their own posters.
- Tinychan + 2ch Mode -