APL Exercises 11
Combinatorial Objects
 

⎕io←0 throughout.
 

11.0 Binary Numbers

There are 2*⍵ binary numbers with ⍵ bits. Write a function to produce the sorted table of ⍵-bit binary numbers.

   B¨ ⍳5
┌┬─┬───┬─────┬───────┐
││0│0 0│0 0 0│0 0 0 0│
││1│0 1│0 0 1│0 0 0 1│
││ │1 0│0 1 0│0 0 1 0│
││ │1 1│0 1 1│0 0 1 1│
││ │   │1 0 0│0 1 0 0│
││ │   │1 0 1│0 1 0 1│
││ │   │1 1 0│0 1 1 0│
││ │   │1 1 1│0 1 1 1│
││ │   │     │1 0 0 0│
││ │   │     │1 0 0 1│
││ │   │     │1 0 1 0│
││ │   │     │1 0 1 1│
││ │   │     │1 1 0 0│
││ │   │     │1 1 0 1│
││ │   │     │1 1 1 0│
││ │   │     │1 1 1 1│
└┴─┴───┴─────┴───────┘
   ⍴¨ B¨ ⍳5
┌───┬───┬───┬───┬────┐
│1 0│2 1│4 2│8 3│16 4│
└───┴───┴───┴───┴────┘

Write another, different, function to do the same. Use cmpx and wsreq to compare their performance.
 

11.1 Gray Code

A Gray code of order ⍵ differs from its neighbor by exactly 1 bit. Write a function to produce the table of Gray codes of order ⍵ .

    G¨ ⍳5
┌┬─┬───┬─────┬───────┐
││0│0 0│0 0 0│0 0 0 0│
││1│0 1│0 0 1│0 0 0 1│
││ │1 1│0 1 1│0 0 1 1│
││ │1 0│0 1 0│0 0 1 0│
││ │   │1 1 0│0 1 1 0│
││ │   │1 1 1│0 1 1 1│
││ │   │1 0 1│0 1 0 1│
││ │   │1 0 0│0 1 0 0│
││ │   │     │1 1 0 0│
││ │   │     │1 1 0 1│
││ │   │     │1 1 1 1│
││ │   │     │1 1 1 0│
││ │   │     │1 0 1 0│
││ │   │     │1 0 1 1│
││ │   │     │1 0 0 1│
││ │   │     │1 0 0 0│
└┴─┴───┴─────┴───────┘
   ⍴¨ G¨ ⍳5
┌───┬───┬───┬───┬────┐
│1 0│2 1│4 2│8 3│16 4│
└───┴───┴───┴───┴────┘

Other Gray code tables are possible, but we want the one which starts from all zeros and proceeds to the next unique and lexicographically least neighbor.
 

11.2 Permutations

Write a function to produce the sorted table of all permutations of ⍵ (that is, permutations of ⍳⍵) for ⍵≥0 . For example:

   perm 3
0 1 2
0 2 1
1 0 2
1 2 0
2 0 1
2 1 0

11.3 Combinations

Write a function to produce the sorted table of all size ⍺ combinations of ⍳⍵ , for ⍺≥0 and ⍵≥⍺ . (The table has shape (⍺!⍵),⍺ .) For example:

   3 comb 5
0 1 2
0 1 3
0 1 4
0 2 3
0 2 4
0 3 4
1 2 3
1 2 4
1 3 4
2 3 4