# Question
Title: Surround a string with "friendliness pellets"
Input a String and surround it with a rounded rectangle of alternating "friendliness pellets".(`0`)

Sandbox

Idea originally from Lyxal.

# Challenge

Given a single line non-empty String of length \\$\<100\\$, print the string with a rounded rectangle of alternating pellets(`0`) around it.

The rectangle must be 11 lines in height.

The first line of the rectangle *must* have at least 1 pellet.

The middle line of the rectangle must be at least 13 characters long. There must be a padding of one space on each side of the text.

Strings smaller than 9 characters must be padded with spaces equally on both sides to fit the above specification. The right side is allowed to have one extra space if the string is of even length.

The template for the output is as follows:

```
      00000..... 6 spaces
    0 4 spaces
  0   2 spaces
 0    1 space
0     no spaces

```

If the string's length is greater than or equal to 9; the first line must have \\$\text{length}-8\\$ pellets.

# Example Input and Output

**Input**:

> Hello World!

**Output**:

```
       0000
     0      0
   0          0
  0            0
 0              0
 0 Hello World! 0
 0              0
  0            0
   0          0
     0      0
       0000

```

**Input**

> 0

**Output**

```
       0
     0   0
   0       0
  0         0
 0           0
 0     0     0
 0           0
  0         0
   0       0
     0   0
       0

```

**Input**

> The quick brown fox

**Output**

```
       00000000000
     0             0
   0                 0
  0                   0
 0                     0
 0 the quick brown fox 0
 0                     0
  0                   0
   0                 0
     0             0
       00000000000

```

**Input**

> In this world, it's KILL or BE killed

**Output**

```
      00000000000000000000000000000
    0                               0
  0                                   0
 0                                     0
0                                       0
0 In this world, it's KILL or BE killed 0
0                                       0
 0                                     0
  0                                   0
    0                               0
      00000000000000000000000000000

```

**Input**

> hi there

**Output**

```
      0
    0   0
  0       0
 0         0
0           0
0 hi there  0
0           0
 0         0
  0       0
    0   0
      0

```

# Example code in Ruby

Try it online!

```
a=[4,2,1,0] # space length to create circle

str=gets.chomp;
l = str.length;
# print first line of pellets
print " "*6
if l<=9 then puts "0" else puts "0"*(l-8) end

# initial pattern
for n in a do
    print " "*n +"0"+" "*(5-n)
    print " " if l<=9
    print " "*(l-8) if l>9
    puts " "*(5-n) +"0"

end

# display string with spaces
if l<9 then puts "0"+" "*((11-l)/2).floor + str + " "*((12-l)/2).ceil + "0" else puts "0 #{str} 0" end

#initial pattern but reversed
for n in a.reverse do
    print " "*n +"0"+" "*(5-n)
    print " " if l<=9
    print " "*(l-8) if l>9
    puts " "*(5-n) +"0"
end

# last line(same as first line)
print " "*6
if l<=9 then puts "0" else puts "0"*(l-8) end

```

# Scoring

This is . Shortest answer in each language wins.

# Answer
> 8 votes
# Charcoal, 40 bytes

```
≔⌈⟦¹⁻Ｌθ⁸⟧η×η0↘↘0→↘00↓00‖ＯＯ←η‖Ｏ↓Ｊ⊘⁻⊖ηＬθ⁵θ

```

Try it online! Link is to verbose version of code. Explanation:

```
≔⌈⟦¹⁻Ｌθ⁸⟧η

```

Calculate the number of `0`s in the top row.

```
×η0

```

Print them.

```
↘↘0→↘00↓00

```

Print the remaining `0`s on the right.

```
‖ＯＯ←η

```

Reflect the additional rows of `0`s to the left, by overlapping the top row of `0`s onto itself.

```
‖Ｏ↓

```

Reflect the `0`s downwards overlapping the middle row.

```
Ｊ⊘⁻⊖ηＬθ⁵θ

```

Calculate the position of the text and print it there. This is necessary for short strings but also avoids dealing with a Charcoal bug whereby an overlapped reflection moves the cursor to the wrong place.

# Answer
> 6 votes
# JavaScript (ES6),  ~~152 139 134~~  133 bytes

```
s=>'64210~01246'.replace(/./g,k=>(g=i=>--i?(d=i+~k,d*=L-i+~k,s[k>g&&(L+n>>1)-i]||d&&k^6|d<0&&' ')+g(i):`
`)(L=(n=s.length)>9?n+5:14))

```

Try it online!

### How?

Given an input string of length \\$n\\$, we define \\$L=\min(14,n+5)\\$. This is the width of the rows of the ASCII art, including the linefeed.

For each line, we store the number of leading spaces in \\$k\\$ and iterate from \\$i=L-1\\$ to \\$i=1\\$. We test the sign of \\$d=(i-k-1)\times(L-i-k-1)\\$ to figure out which character must be drawn.

We always draw a space if \\$d\\$ is negative and a zero if \\$d=0\\$. If \\$d\\$ is positive, we draw a zero if \\$k=6\\$ (top and bottom borders) or a space otherwise (inner cells). The middle line is a special case where we attempt to get the character from the input string, at the position \\$\lfloor (L+n)/2\rfloor-i\\$.

For `"Hello World!"`, we have \\$n=12\\$ and \\$L=17\\$. This gives:

```
    1      0
i = 6543210987654321
    ------0++0------  k = 6
    ----0++++++0----  k = 4
    --0++++++++++0--  k = 2
    -0++++++++++++0-  k = 1
    0++++++++++++++0  k = 0
    0+Hello World!+0  k = 0
    0++++++++++++++0  k = 0
    -0++++++++++++0-  k = 1
    --0++++++++++0--  k = 2
    ----0++++++0----  k = 4
    ------0++0------  k = 6

```

### Commented

```
s =>                         // s = input string
'64210~01246'.replace(       // replace in the string '64210~01246'
  /./g, k => (               // each character k:
    g = i =>                 //   g is a recursive function taking a counter i:
      --i ?                  //     decrement i; if it's not 0:
        ( d = i + ~k,        //       d = i - k - 1
          d *= L - i + ~k,   //       d = (i - k - 1) * (L - i - k - 1)
          s[                 //       extract from s:
            k > g &&         //         if k is '~':
            (L + n >> 1) - i //           use floor((L + n) / 2) - i
                             //         otherwise, use false
                             //         (leading to s[false] == undefined)
          ]                  //       end of lookup in s
          ||                 //       if it's undefined:
            d &&             //         use '0' if d = 0
            k ^ 6 | d < 0    //         or k is equal to 6 and d is non-negative
            && ' '           //         otherwise, use a space
        ) + g(i)             //       append the result of a recursive call
      :                      //     else:
        `\n`                 //       append a linefeed and stop the recursion
  )(                         //   initial call to g:
    L = (n = s.length) > 9 ? //     if the length n of s is greater than 9:
      n + 5                  //       define L = n + 5
    :                        //     else:
      14                     //       define L = 14
  )                          //
)                            // end of replace()

```

# Answer
> 5 votes
# 05AB1E, ~~64~~ 54 bytes

```
4Å0Îg9‚à8-©;î×šŽüÎSú.B®Éi.ºëº}I11Ig-;1‚à©ú®îð×«0.øª».∊

```

Try it online or verify all test cases.

**Explanation:**

```
4Å0                   # Push a list of 4 0s: [0,0,0,0]
   Î                  # Push 0 and the input-string
    g                 # Pop the input, and push its length
     9‚à              # Pair with 9, and pop and push the maximum
        8-            # Subtract 8
          ©           # Store this in variable `®` (without popping)
           ;          # Halve it
            î         # Ceil it
             ×        # Create a string of that many 0s
              š       # Prepend it at the front of the [0,0,0,0]-list
ŽüÎ                   # Push compressed integer 64210
   S                  # Convert it to a list of digits: [6,4,2,1,0]
    ú                 # Pad that many leading spaces to the list of 0s
.B                    # Box it, which adds trailing spaces to each string to equal
                      # their lengths
®Éi                   # If the value `®` is odd:
   .º                 #  Mirror each line with the last character overlapping
  ë                   # Else (it's even instead):
   º                  #  Mirror each line without overlapping
  }                   # Close the if-else statement
I                     # Push the input-string again
 11                   # Push 11
   Ig-                # Subtract the input-length from it
      ;               # Halve it
       1‚à            # Pair with 1, and pop and push the maximum
          ©           # Store it in variable `®` (without popping)
           ú          # Pad that many leading spaces to the input
            ®         # Push `®` again
             î        # Ceil it
              ð×«     # Pad that many trailing spaces
                 0.ø  # Then surround it with leading/trailing 0
                    ª # And append it to the list of strings
»                     # Join the lines by newlines
 .∊                   # And mirror the entire string vertically with overlap
                      # (after which the result is output implicitly)

```

See this 05AB1E tip of mine (section *How to compress large integers?*) to understand why `ŽüÎ` is `64210`.

# Answer
> 3 votes
# Jelly, 52 bytes

```
³L>9ȯ
L11_»2⁶ẋŒHṚjµL_⁽|hḤD©Ḥ¤⁶ẋ;W¬1¦Ø0j0ç?Ɱ⁶ẋ®¤;"ŒḄY

```

A full program which prints the result.

**Try it online!**

### How?

```
³L>9ȯ - Link 1: unused argument; list of characters, Y
³     - program argument, the given text (same as T in the main Link)
 L    - length
  >9  - greater than nine?
    ȯ - logical OR with Y

L11_»2⁶ẋŒHṚjµL_⁽|hḤD©Ḥ¤⁶ẋ;W¬1¦Ø0j0ç?Ɱ⁶ẋ®¤;"ŒḄY - Main Link: list of characters, T
L                                              - length
 11_                                           - 11 - that
    »2                                         - max of that and two
      ⁶ẋ                                       - that many spaces
        ŒH                                     - split in two
          Ṛ                                    - reverse (get longer part on the right)
           j                                   - join with T
            µ                                  - start a new monadic chain - f(X=that)
                      ¤                        - nilad followed by link(s) as a nilad:
               ⁽|h                             -   32105
                  Ḥ                            -   double -> 64210
                   D                           -   digits -> [6,4,2,1,0]
                    ©                          -   store in register
                     Ḥ                         -   double -> [12,8,4,2,0]
             L_                                - length (X) minus that (vectorises)
                       ⁶ẋ                      - that many spaces (vectorises)
                          W                    - wrap X in a list
                         ;                     - concatenate
                           ¬1¦                 - logical NOT first line
                                                   (changing spaces to 0s)
                              Ø0               - [0,0]
                                    Ɱ          - map across the lines with:
                                   ?           -   if...
                                  ç            -   ...condition: call Link 1 f([0,0], line)
                                j              -   ...then: ([0,0]) join with (line)
                                 0             -   ...else a single zero
                                        ¤      - nilad followed by link(s) as a nilad:
                                     ⁶         -   space
                                       ®       -   recall from register -> [6,4,2,1,0]
                                      ẋ        -   repeat (vectorises)
                                         ;"    - zip with concatenation
                                                   (prefix lines with spaces)
                                           ŒḄ  - bounce (reflect top lines to the bottom)
                                             Y - join with newlines
                                               - implicit print

```

# Answer
> 3 votes
# Python 3, 134 bytes

```
lambda s:'\n'.join(f'{0:{i}}{0**i*s:{"0 "[i<6]}^{max(i*2,len(s)+4,13)-(i*2or 2)}}'+'0'[i+i>10>len(s):]for i in(7,5,3,2,1,0,1,2,3,5,7))

```

Try it online!

# Answer
> 2 votes
# Perl 5, 155 bytes

```
sub f{$_=pop;substr$r=64210001246=~s,.,$"x$&.($&-6?0 .$"x(11-$&*2).0:0).$/,ger=~s,^.{6}(.),($l=y|||c-9)>0?$&.$1x$l:$&,mger,$l>0?59+5*$l:59-$l/2,$l+9,$_;$r}

```

Try it online!

Slightly ungolfed:

```
sub f{
  $_=pop;                           # $_ = input text
  substr                            # args: string, offset, length, replacement
    $r=                             # $r = result string init to empty rectangle
      64210001246                   # digits are spaces before first 0 each line
        =~s,.,$"x$&.($&-6?0 .$"x(11-$&*2).0:0).$/,ger
        =~s,^.{6}(.),($l=y|||c-9)>0?$&.$1x$l:$&,mger,
    $l>0 ? 59+5*$l : 59-$l/2,       # insert input text at this position
    $l+9,                           # ...this length ($l=input length minus 9)
    $_;                             # replacement = input
  $r                                # return result
}

```

# Answer
> 1 votes
# Python 3.8 (pre-release), 158 bytes

```
lambda s:'\n'.join((e:=[" "*6+"0"*(l:=len(b:=(c:=9-len(s))//2*' '+s+(c//2+c%2)*' ')-8),*[i*" "+"0"+" "*(l+10-2*i)+"0"for i in[4,2,1,0]],f'0 {b} 0'])+e[4::-1])

```

Try it online!

---
Tags: code-golf, string, ascii-art
---


title: Sort numbers by binary 1's count

text:
# Question
Title: Sort numbers by binary 1's count
### Goal

Write a function or program sort an array of integers in descending order by the number of 1's present in their binary representation. No secondary sort condition is necessary.

### Example sorted list

(using 16-bit integers)

```
  Dec                Bin        1's
16375   0011111111110111        13
15342   0011101111101110        11
32425   0111111010101001        10
11746   0010110111100010         8
28436   0000110111110100         8
19944   0100110111101000         8
28943   0000011100011111         8
 3944   0000011111101000         7
15752   0011110110001000         7
  825   0000000011111001         6
21826   0101010101000010         6

```

### Input

An array of 32-bit integers.

### Output

An array of the same integers sorted as described.

### Scoring

This is code golf for the least number of bytes to be selected in one week's time.

# Answer
> 28 votes
## J (11)

```
(\:+/"1@#:)

```

This is a function that takes a list:

```
     (\:+/"1@#:) 15342 28943 16375 3944 11746 825 32425 28436 21826 15752 19944
16375 15342 32425 28943 11746 28436 19944 3944 15752 825 21826

```

If you want to give it a name, it costs one extra character:

```
     f=:\:+/"1@#:
     f 15342 28943 16375 3944 11746 825 32425 28436 21826 15752 19944
16375 15342 32425 28943 11746 28436 19944 3944 15752 825 21826

```

Explanation:

* `\:`: downwards sort on
* `+/`: sum of
* `"1`: each row of
* `#:`: binary representation

# Answer
> 17 votes
# JavaScript, 39

**Update:** Now shorter than Ruby.

```
x.sort(q=(x,y)=>!x|-!y||q(x&x-1,y&y-1))

```

**40**

```
x.sort(q=(x,y)=>x&&y?q(x&x-1,y&y-1):x-y)

```

Explanation:

q is a recursive function. If x or y are 0, it returns `x-y` (a negative number if x is zero or a positive number if y is zero). Otherwise it removes the lowest bit (`x&x-1`) from x and y and repeats.

**Previous version (42)**

```
x.sort(q=(x,y)=>x^y&&!x-!y+q(x&x-1,y&y-1))

```

# Answer
> 16 votes
# Ruby 41

```
f=->a{a.sort_by{|n|-n.to_s(2).count(?1)}}

```

Test:

```
a = [28943, 825, 11746, 16375, 32425, 19944, 21826, 15752, 15342, 3944, 28436];
f[a]
=> [16375, 15342, 32425, 11746, 28436, 28943, 19944, 15752, 3944, 21826, 825]

```

# Answer
> 8 votes
## Python 3 (44):

```
def f(l):l.sort(lambda n:-bin(n).count('1'))

```

# Answer
> 8 votes
## Common Lisp, 35

`logcount` returns the number of ‘on’-bits in a number. For a list `l`, we have:

```
(sort l '> :key 'logcount)

```

```
CL-USER> (sort (list 16375 15342 32425 11746 28436 19944 28943 3944 15752 825 21826) '> :key 'logcount)
;=> (16375 15342 32425 11746 28436 19944 28943 3944 15752 825 21826)

```

As a standalone function, and what I'll base the byte count on:

```
(lambda(l)(sort l'> :key'logcount))

```

# Answer
> 7 votes
# Python 3, ~~90~~ ~~77~~ ~~72~~ 67 characters.

Our solution takes an input from the command-line, and prints the number in descending order (67 chars), or ascending (66).

**Descending order**

```
print(sorted(input().split(),key=lambda x:-bin(int(x)).count("1"))) # 67

```

Thanks to **@daniero**, for the suggestion of using a minus in the 1's count to reverse it, instead of using a slice to reverse the array at the end! This effectively saved 5 characters.

Just for the sake of posting it, the ascending order version (which was the first we made) would take one character less.

**Ascending order**:

```
print(sorted(input().split(),key=lambda x:bin(int(x)).count("1"))) # 66

```

Thanks to **@Bakuriu** for the *key=lambda x…* suggestion. ;D

# Answer
> 7 votes
## JavaScript \[76 bytes\]

```
a.sort(function(x,y){r='..toString(2).split(1).length';return eval(y+r+-x+r)})

```

where `a` is an input array of numbers.

**Test:**

```
[28943,825,11746,16375,32425,19944,21826,15752,15342,3944,28436].sort(function(x, y) {
    r = '..toString(2).split(1).length';
    return eval(y + r + -x + r);
});

[16375, 15342, 32425, 19944, 11746, 28943, 28436, 15752, 3944, 21826, 825]

```

# Answer
> 6 votes
## Mathematica 30

```
SortBy[#,-DigitCount[#,2,1]&]&

```

Usage:

```
SortBy[#,-DigitCount[#,2,1]&]&@
                           {19944,11746,15342,21826,825,28943,32425,16375,28436,3944,15752}

```

> {16375, 15342, 32425, 11746, 19944, 28436, 28943, 3944, 15752, 825, 21826}

# Answer
> 6 votes
# k \[15 Chars\]

```
{x@|<+/'0b\:'x}

```

### Example 1

```
{x@|<+/'0b\:'x}19944, 11746, 15342, 21826, 825, 28943, 32425, 16375, 28436, 3944, 15752

16375 15342 32425 28436 28943 11746 19944 15752 3944 825 21826

```

### Example 2 (all numbers are 2^n -1)

```
{x@|<{+/0b\:x}'x}3 7 15 31 63 127

127 63 31 15 7 3

```

# Answer
> 5 votes
# Java 8 - ~~87/113~~ ~~81/111~~ ~~60/80~~ 60/74/48 characters

This is not a complete java program, it is just a function (a method, to be exact).

It assumes that `java.util.List` and `java.lang.Long.bitCount` are imported, and has 60 characters:

```
void s(List<Long>a){a.sort((x,y)->bitCount(x)-bitCount(y));}

```

If no pre-imported stuff are allowed, here it is with 74 characters:

```
void s(java.util.List<Long>a){a.sort((x,y)->x.bitCount(x)-x.bitCount(y));}

```

Add more 7 characters if it would be required that it should be `static`.

\[4 years later\] Or if you prefer, it could be a lambda (thanks @KevinCruijssen for the suggestion), with 48 bytes:

```
a->{a.sort((x,y)->x.bitCount(x)-x.bitCount(y));}

```

# Answer
> 5 votes
# Mathematica 39

`IntegerDigits[#,2]` converts a base 10 number to list of 1's and 0's.

`Tr` sums the digits.

```
f@n_:=SortBy[n,-Tr@IntegerDigits[#,2]&]

```

**Test Case**

```
f[{19944, 11746, 15342, 21826, 825, 28943, 32425, 16375, 28436, 3944, 15752}]

```

> {16375, 15342, 32425, 11746, 19944, 28436, 28943, 3944, 15752, 825, 21826}

# Answer
> 4 votes
# Python 2.x - 65 characters (bytes)

```
print sorted(input(),key=lambda x:-sum(int(d)for d in bin(x)[2:]))

```

That's actually 66 characters, 65 if we make it a function (then you need something to call it which is lamer to present).

```
f=lambda a:sorted(a,key=lambda x:-sum(int(d)for d in bin(x)[2:]))

```

Demo in Bash/CMD:

```
echo [16, 10, 7, 255, 65536, 5] | python -c "print sorted(input(),key=lambda x:-sum(int(d)for d in bin(x)[2:]))"

```

# Answer
> 4 votes
# Matlab, 34

Input in 'a'

```
[~,i]=sort(-sum(dec2bin(a)'));a(i)

```

Works for nonnegative numbers.

# Answer
> 4 votes
## **C - 85 bytes (~~108~~ 106 bytes)**

Portable version on GCC/Clang/wherever `__builtin_popcount` is available (106 bytes):

```
#define p-__builtin_popcount(
c(int*a,int*b){return p*b)-p*a);}
void s(int*n,int l){qsort(n,l,sizeof l,c);}

```

Ultra-condensed, non-portable, barely functional MSVC-only version (85 bytes):

```
#define p __popcnt
c(int*a,int*b){return p(*b)-p(*a);}
s(int*n,int l){qsort(n,l,4,c);}         /* or 8 as needed */

```

---

* First newline included in byte count because of the `#define`, the others are not necessary.
* Function to call is `s(array, length)` according to specifications.
* Can hardcode the `sizeof` in the portable version to save another 7 characters, like a few other C answers did. I'm not sure which one is worth the most in terms of length-usability ratio, you decide.

# Answer
> 4 votes
# PowerShell v3, ~~61~~ ~~58~~ 53

```
$args|sort{while($_){if($_-band1){1};$_=$_-shr1}}-des

```

The ScriptBlock for the `Sort-Object` cmdlet returns an array of 1's for each 1 in the binary representation of the number. `Sort-Object` sorts the list based on the length of the array returned for each number.

To execute:

```
script.ps1 15342 28943 16375 3944 11746 825 32425 28436 21826 15752 19944

```

# Answer
> 3 votes
# ECMAScript 6, 61

Assumes `z` is the input

```
z.sort((a,b)=>{c=d=e=0;while(++c<32)d+=a>>c&1,e+=b>>c&1},e-d)

```

Test data

```
[28943,825,11746,16375,32425,19944,21826,15752,15342,3944,28436].sort(
    (a,b)=>{
        c=d=e=0;
        while(++c<32)
            d+=a>>c&1,e+=b>>c&1
    },e-d
)

[16375, 15342, 32425, 11746, 19944, 28436, 28943, 15752, 3944, 21826, 825]

```

Thanks, toothbrush for the shorter solution.

# Answer
> 3 votes
# , ~~132~~ ~~96~~ ~~94~~ ~~88~~ ~~84~~ ~~75~~ ~~73~~ ~~53~~ 51 bytes

-20 thanks to J.Doe's implementation -2 more thanks to Giuseppe

```
function(x)x[order(colSums(sapply(x,intToBits)<1))]

```

My original post:

```
pryr::f(rev(x[order(sapply(x,function(y)sum(as.double(intToBits(y)))))]))

```

Try it online!

I tried several different methods before I got down to this result.

**Matrix Method:** Created a two column matrix, one column with the input vector, one of the sum of the binary representation, then I sorted on the sum of binary.

```
function(x){m=matrix(c(x,colSums(sapply(x,function(y){as.integer(intToBits(y))}))),nc=2,nr=length(x));m[order(m[,2],decreasing=T),]}

```

**Non-Matrix:** Realized I could toss out the matrix function and instead create a vector of binary values, sum them, order them, then use the ordered values to reorder the input vector.

```
function(x){m=colSums(sapply(x,function(y){as.integer(intToBits(y))}));x[order(m,decreasing=T)]}

```

**Minor Changes**

```
function(x){m=colSums(sapply(x,function(y)as.double(intToBits(y))));x[order(m,decreasing=T)]}

```

**More Minor Changes** Converting entire thing to one line of code instead of two separated by a semicolon.

```
function(x)x[order(colSums(sapply(x,function(y)as.double(intToBits(y)))),decreasing=T)]

```

**Sum Method** Instead of adding the columns with `colSums` of the binary matrix created by `sapply`, I added the elements in the column before `sapply` "finished."

```
function(x)x[order(sapply(x,function(y)sum(as.double(intToBits(y)))),decreasing=T)]

```

**Decreasing to Rev** I really wanted to shorten decreasing, but R squawks at me if I try to shorten `decreasing` in the `order` function, which was necessary to get the order desired as `order` defaults to increasing, then I remembered the `rev` function to reverse a vector. **EUREKA!!!** The last change in the final solution was `function` to `pryr::f` to save 2 more bytes

```
function(x)rev(x[order(sapply(x,function(y)sum(as.double(intToBits(y)))))])

```

# Answer
> 2 votes
# Haskell, 123C

```
import Data.List
import Data.Ord
b 0=[]
b n=mod n 2:b(div n 2)
c n=(n,(sum.b)n)
q x=map fst$sortBy(comparing snd)(map c x)

```

This is the first way I thought of solving this, but I bet there's a better way to do it. Also, if anyone knows of a way of golfing Haskell imports, I would be very interested to hear it.

## Example

```
*Main> q [4,2,15,5,3]
[4,2,5,3,15]
*Main> q [7,0,2]
[0,2,7]

```

## Ungolfed version (with explanations)

```
import Data.List
import Data.Ord

-- Converts an integer into a list of its bits
binary 0 = []
binary n = mod n 2 : binary (div n 2)

-- Creates a tuple where the first element is the number and the second element
-- is the sum of its bits.
createTuple n = (n, (sum.binary) n)

-- 1) Turns the list x into tuples
-- 2) Sorts the list of tuples by its second element (bit sum)
-- 3) Pulls the original number out of each tuple
question x = map fst $ sortBy (comparing snd) (map createTuple x)

```

# Answer
> 2 votes
# Julia 1.0, 41 bytes

```
a->sort(a,by=x->sum((x>>n)&1 for n=0:63))

```

Try it online!

# Answer
> 2 votes
**DFSORT** (IBM Mainframe sorting product) **288** (each source line is 72 characters, must have space in position one)

```
 INREC IFTHEN=(WHEN=INIT,BUILD=(1,2,1,2,TRAN=BIT)),
       IFTHEN=(WHEN=INIT,FINDREP=(STARTPOS=3,INOUT=(C'0',C'')))
 SORT FIELDS=(3,16,CH,D)
 OUTREC BUILD=(1,2)

```

Just for fun, and no mathematics.

Takes a file (could be executed from a program which used an "array") with the integers. Before sorting, it translates the integers to bits (in a 16-character field). Then changes the 0s in the bits to nothing. SORT Descending on the result of the changed bits. Creates the sorted file with just the integers.

# Answer
> 2 votes
# Smalltalk (Smalltalk/X), 36 (or maybe 24)

input in a; destructively sorts in a:

```
a sort:[:a :b|a bitCount>b bitCount]

```

functional version: returns a new sorted array:

```
a sorted:[:a :b|a bitCount>b bitCount]

```

there is even a shorter variant (passing the *name* or the function as argument) in 24 chars. But (sigh) it will sort highest last. As I understood, this was not asked for, so I don't take that as golf score:

```
a sortBySelector:#bitCount

```

# Answer
> 2 votes
# CoffeeScript (94)

Readable code (212):

```
sort_by_ones_count = (numbers) ->
  numbers.sort (a, b) ->
    a1 = a.toString(2).match(/1/g).length
    b1 = b.toString(2).match(/1/g).length
    if a1 == b1
      0
    else if a1 > b1
      1
    else
      -1

console.log sort_by_ones_count [825, 3944, 11746, 15342, 15752, 16375, 19944, 21826, 28436, 28943, 32425]

```

Optimized (213):

```
count_ones = (number) -> number.toString(2).match(/1/g).length
sort_by_ones_count = (numbers) -> numbers.sort (a, b) ->
  a1 = count_ones(a)
  b1 = count_ones(b)
  if a1 == b1 then 0 else if a1 > b1 then 1 else -1

```

Obfuscating (147):

```
c = (n) -> n.toString(2).match(/1/g).length
s = (n) -> n.sort (a, b) ->
  a1 = c(a)
  b1 = c(b)
  if a1 == b1 then 0 else if a1 > b1 then 1 else -1

```

Ternary operators are excessively long (129):

```
c = (n) -> n.toString(2).match(/1/g).length
s = (n) -> n.sort (a, b) ->
  a1 = c(a)
  b1 = c(b)
  (0+(a1!=b1))*(-1)**(0+(a1>=b1))

```

Too long yet, stop casting (121):

```
c = (n) -> n.toString(2).match(/1/g).length
s = (n) -> n.sort (a, b) ->
  a1 = c(a)
  b1 = c(b)
  (-1)**(a1>=b1)*(a1!=b1)

```

Final (94):

```
c=(n)->n.toString(2).match(/1/g).length
s=(n)->n.sort((a, b)->(-1)**(c(a)>=c(b))*(c(a)!=c(b)))

```

# Answer
> 2 votes
# Scala, 58

```
def c(l:List[Int])=l.sortBy(-_.toBinaryString.count(_>48))

```

# Answer
> 2 votes
# PHP 5.4+ 131

I don't even know why I bother with PHP, in this case:

```
<?unset($argv[0]);usort($argv,function($a,$b){return strcmp(strtr(decbin($b),[0=>'']),strtr(decbin($a),[0=>'']));});print_r($argv);

```

Usage:

```
> php -f sortbybinaryones.php 15342 28943 16375 3944 11746 825 32425 28436 21826 15752 19944
Array
(
    [0] => 16375
    [1] => 15342
    [2] => 32425
    [3] => 28436
    [4] => 19944
    [5] => 11746
    [6] => 28943
    [7] => 3944
    [8] => 15752
    [9] => 825
    [10] => 21826
)

```

# Answer
> 2 votes
# C

```
void main()
{
 int a[]={7,6,15,16};
 int b,i,n=0;
 for(i=0;i<4;i++)
 {  for(b=0,n=0;b<=sizeof(int);b++)
      (a[i]&(1<<b))?n++:n;
    a[i]=n;
 }
 for (i = 1; i < 4; i++)
  {   int tmp = a[i];
      for (n = i; n >= 1 && tmp < a[n-1]; n--)
         a[n] = a[n-1];
      a[n] = tmp;
  }
}

```

# Answer
> 2 votes
# C#, 88 89

```
int[] b(int[] a){return a.OrderBy(i=>-Convert.ToString(i,2).Count(c=>c=='1')).ToArray();}

```

Edit: descending order adds a character.

# Answer
> 2 votes
# ECMAScript 6 (61 characters):

```
_=_=>_.toString(2).replace(/0/g,'');x.sort((a,b)=>_(b)-_(a))

```

*Expects the input array to be in `x`.*

# Answer
> 2 votes
## **Javascript** 84

Inspired by other javascript answers, but without eval and regex.

```
var r=(x)=>(+x).toString(2).split('').reduce((p,c)=>p+ +c)
[28943,825,11746,16375,32425,19944,21826,15752,15342,3944,28436].sort((x,y)=>r(x)-r(y));

```

# Answer
> 2 votes
# C - ~~124~~ 111

Implemented as a method and using the standard library for the sorting. A pointer to the array and the size should be passed as parameters. This will only work on systems with 32-bit pointers. On 64-bit systems, some characters have to be spent specifying pointer definitions.

Indentation for readability

```
c(int*a,int*b){
    int d,e,i;
    for(d=e=i=0;i-32;){
        d+=*a>>i&1;e+=*b>>i++&1;
    }
    return d>e?-1:d<e;
}
o(r,s){qsort(r,s,4,c);}

```

Sample call:

```
main() {
    static int a[] ={1, 2, 3, 4, 5, 6, 7, 8, 9};
    o(a, 9);
}

```

# Answer
> 2 votes
Javascript (82)

```
a.sort(function(b,c){q=0;while(b|c){b%2?c%2?0:q++:c%2?q--:0;b>>=1;c>>=1}return q})

```

# Answer
> 2 votes
## Postscript, 126

Because list of values by which we sort is known beforehand and very limited (32), this task can be easily done even if there's no built-in for sorting, by picking matching values for 1..32. (Is it O(32n)? Probably).

Procedure expects array on stack and returns 'sorted' array.

```
/sort_by_bit_count {
    [ exch
    32 -1 1 {
        1 index
        {
            dup 2 32 string cvrs
            0 exch
            {48 sub add} forall
            2 index eq
            {3 1 roll} {pop} ifelse
        } forall
        pop
    } for
    pop ]
} def

```

Or, ritually stripped of white space and readability:

```
/s{[exch 32 -1 1{1 index{dup 2 32 string cvrs 0 exch{48 sub add}forall 2 index eq{3 1 roll}{pop}ifelse}forall pop}for pop]}def

```

Then, if saved to `bits.ps` it can be used like this:

```
gs -q -dBATCH bits.ps -c '[(%stdin)(r)file 1000 string readline pop cvx exec] s =='
825 3944 11746 15342 15752 16375 19944 21826 28436 28943 32425
[16375 15342 32425 11746 19944 28436 28943 3944 15752 825 21826]

```

I think it effectively is the same as this Perl (there's yet no Perl here, too):

```
sub f{map{$i=$_;grep{$i==(()=(sprintf'%b',$_)=~/1/g)}@_}reverse 1..32}

```

Though *that*, unlike Postscript, can be easily golfed:

```
sub f{sort{j($b)-j($a)}@_}sub j{$_=sprintf'%b',@_;()=/1/g}

```

# Answer
> 2 votes
# Java 8: 144

```
static void main(String[]a){System.out.print(Stream.of(a).mapToInt(Integer::decode).sorted(Comparable.comparing(Integer::bitCount)).toArray());}

```

In expanded form:

```
static void main(String[] args){
    System.out.print(
        Stream.of(args).mapToInt(Integer::decode)
              .sorted(Comparable.comparing(Integer::bitCount))
              .toArray()
        );
}

```

As you can see, this works by converting the `args` to a `Stream<String>`, then converting to a `Stream<Integer>` with the `Integer::decode` function reference (shorter than `parseInt` or `valueOf`), and then sorting by `Integer::bitCount`, then putting it in an array, and printing it out.

Streams make everything easier.

# Answer
> 2 votes
# PowerShell v2 or later, 44

```
sort{[convert]::ToString($_,2)-replace0}-des

```

The long version:

```
Sort-Object -Property {[convert]::ToString($_, 2) -replace '0', ''} -Descending

```

"sort" is a default alias for the Sort-Object cmdlet.
Sort-Object allows sorting the incoming list by evaluating an expression on the fly, which is the script block inside the curly braces.
The .NET class "Convert" is used to convert the incoming integer ("$\_") into its binary string representation.
The "-replace" Operator will then remove all zeros, so that only a string of ones remains (the string "Replace()" method would have worked, too, but would have been longer).
Since these strings all consist of the same character, they'll be sorted by length, ascending by default. The switch argument "Descending" will reverse the order, and since there's another argument 'Debug', the first three characters are required for PowerShell to identify the switch.

The list to sort is expected in the pipeline/stdin, for example:

```
$l = 15342, 28943, 16375, 3944, 11746, 825, 32425, 28436, 21826, 15752, 19944
$l | sort{[convert]::ToString($_,2)-replace0}-des

```

Sort-Object
https://docs.microsoft.com/en-us/powershell/module/microsoft.powershell.utility/sort-object?view=powershell-6

Convert Class
https://msdn.microsoft.com/en-us/library/system.convert(v=vs.110).aspx

# Answer
> 2 votes
# 05AB1E, 4 bytes

```
ΣbSO

```

Try it online!

# Answer
> 2 votes
# Perl 6, 27 bytes

```
*.sort(-*.base(2).comb.sum)

```

Try it online!

# Answer
> 1 votes
# C#, ~~191~~ ~~183~~ 172 thanks to Rik

```
 using System.Linq;class P{static void Main(string[]a){System.Console.WriteLine(string.Join(" ",a.Select(int.Parse).OrderBy(v=>{int c=0;for(;v>0;c++,v&=v-1);return-c;})));}}

```

Formatted:

```
using System.Linq;
class P
{
    static void Main(string[] a)
    {
        System.Console.WriteLine(string.Join(" ", a.Select(int.Parse)
            .OrderBy(v => {
                int c = 0;
                for (; v > 0; c++, v &= v - 1);
                return -c;
            })
        ));
    }
}

```

When run as `foo.exe 32425 28943 28436 21826 19944 16375 15752 15342 11746 3944 825` the output is:

```
16375 15342 32425 28943 28436 19944 11746 15752 3944 21826 825

```

Including the bitcount:

```
16375   13
15342   11
32425   10
28943   8
28436   8
19944   8
11746   8
15752   7
3944    7
21826   6
825     5

```

# As function only: ~~100~~ 89 chars

...Which some seem to regard as correct too:

```
int[] v(int[]a){return a.OrderBy(v=>{int c=0;for(;v>0;c++,v&=v-1);return-c;}).ToArray();}

```

To use, call `v()` with an array of ints to be sorted by binary 1's count.

# Answer
> 1 votes
# C++ and QT

```
template<typename T>

//Compars the number of ones in the binary representation of some numbers
bool onesCountSort()(Const T* a, const T* b) const
{
   int aCount = getOnesCount(&a);
   int bCount = getOnesCount(&b);
   return aCount < bCount;
}

//Returns the number of ones in a number
int getOnesCount(T value) const
{
    int rVal = 0;
    while(value > 0)
    {
       rVal++;
       value = value >> 1;
    }
    return rVal;
}

int main(int argc, char *argv[])
{
   QList<int> listTest;
   listTest << 16375;
   listTest << 15342;
   listTest << 32425;
   listTest << 11746;
   listTest << 28436;
   //...

   qSort(list.begin(); list.end(), onesCountSort<int>());//Sort by binary ones count
   qSort(list.end(); list.begin(), onesCountSort<int>());//Reverse the sort
}

```

## Edit:

```
template<typename T>

//Compars the number of ones in the binary representation of some numbers
bool onesCountSort()(Const T* a, const T* b) const
{
   return getOnesCount(a) < getOnesCount(b);
}

int getOnesCount(const T* value, int count = 0) const
{
    return &value ? count : getOnesCount(value >> 1, count + 1);
}

```

# Answer
> 1 votes
## GolfScript, 14 chars

```
~{2base 0-,}$`

```

Example input (sorted in numerical order):

```
[825 3944 11746 15342 15752 16375 19944 21826 28436 28943 32425]

```

Example output (sorted by bit count) for the input above:

```
[825 21826 15752 3944 28436 28943 19944 11746 32425 15342 16375]

```

Note that the program above sorts the input in ascending order by bit count. If you insist on descending order, that'll cost one extra char:

```
~{2base 0-,~}$`

```

**Explanation:**

* `~` evals the input. Since you didn't specify the input format, I took the liberty of assuming that the input is provided as a GolfScript array literal (i.e. a series of whitespace-separated numbers wrapped in `[ ]`).
* `{ }$` applies the code inside the braces to each element of the array, and sorts them according to the resulting sort keys.

+ Inside the braces, `2base` uses the built-in base conversion operator to turn the number into an array of bits (e.g. `19``[1 0 0 1 1]`). The `0-` then removes all the zero bits from the array (the space before it is needed to keep `base0` from being parsed as a single token) and the `,` counts the length of the remaining array.
    + (In the descending order version, the `~` then bitwise negates the count, effectively applying the map *x* ↦ −(*x* \+ 1) and thus inverting the sort order.)
* Finally, the ``` un-evals the sorted array, converting it back into the input format for output.

# Answer
> 1 votes
\**

## C++(Visual Studio 2013), 112

\**

```
#define n int
#define s __popcnt
n* d(n i[], n l){sort(i, i+l, [](n a, n b){return  s(a) > s(b); });return i;}

```

Unobfuscated:

```
#define n int
#define s __popcnt
n* d(n i[], n l){
    std::sort(i, i+l, [](n a, n b){return  s(a) > s(b); });
    return i;
}

```

haven't touched C++ for a while. While not the shortest, it PROBABLY is the fastest, by far, though it depends highly if the \__popcnt is implemented as single CPU instruction, or set.

I might fire up mathbrain later and see if it's possible to compare two numbers by bits and see which one has more bits set(without any string conversions or bit counting). I think there is some kind of bit-hack that can be used, but it's probably longer.

# Answer
> 1 votes
**C : 112**

```
C(a){int c=a!=0;while(a&=a-1)c++;return c;}
B(int*a,int*b){return C(*b)-C(*a);}
S(int*a,int n){qsort(a,n,4,B);}

```

works on gcc with `Target: x86_64-linux-gnu`

usage: `S(array, size);`

# Answer
> 1 votes
**Haskell - 107100 (including sample list and main call) else 100-22=78**

```
import Data.List
b 0=0
b n=mod n 2+b(div n 2)
c q=map snd$ sort$ zip(map b q)q
main=print$ c [1..100]

```

Result:

```
[1,2,4,8,16,32,64,3,5,6,9,10,12,17,18,20,24,33,34,36,40,48,65,66,68,72,80,96,7,11,13,14,19,21,22,25,26,28,35,37,38,41,42,44,49,50,52,56,67,69,70,73,74,76,81,82,84,88,97,98,100,15,23,27,29,30,39,43,45,46,51,53,54,57,58,60,71,75,77,78,83,85,86,89,90,92,99,31,47,55,59,61,62,79,87,91,93,94,63,95]

```

# Answer
> 1 votes
## C, 95 chars

Call `s(array, size)` to sort an array.
The framework is based on AShelly's answer, with a different bit count function.
Only works on 32bit platforms.

```
c(unsigned a){return a?a%2+c(a/2):0;}
f(int*a,int*b){return c(*b)-c(*a);}
s(a,n){qsort(a,n,4,f);}

```

The bit count function treats the numbers as unsigned, so division will discard the low bit.

# Answer
> 1 votes
# php 5.3, 117 109

Thank to @mniip to point out some more char save. So New One are

```
usort($a,function($u,$v){return $u==$v?0:(substr_count(decbin($u),'1')<substr_count(decbin($v),'1')?1:-1);});

```

Older One

```
usort($a,function($u,$v){if($u==$v)return 0;return substr_count(decbin($u),'1')<substr_count(decbin($v),'1')?1:-1;});

```

# Answer
> 1 votes
# K, 14

```
{x@>+/'0b\:'x}

```

.

```
k){x@>+/'0b\:'x} 28943 16375 15342
16375 15342 28943

```

# Answer
> 1 votes
**Javascript (ECMAScript 6) - 41 Characters**

Takes an array `a` as input:

```
a.sort(ພ=(ຟ,ຝ)=>ຟ*ຝ?ພ(ຟ&ຟ-1,ຝ&ຝ-1):(ຝ-ຟ))

```

Testing (with less obfuscated code):

JSFIDDLE

```
a=[19944, 11746, 15342, 21826, 825, 28943, 32425, 16375, 28436, 3944, 15752];
a.sort(_=(b,c)=>b*c?_(b&b-1,c&c-1):(c-b))
console.log(a.toString());

```

Gives this output:

```
16375,15342,32425,19944,11746,28943,28436,3944,15752,21826,825

```

# Answer
> 1 votes
# C# - 98

C# can't really compete in "the smallest" category. Still fun, though :)

```
x.Select(i=>new{v=i,c=Convert.ToString(i,2).Count(c=>c=='1')}).OrderByDescending(a=>a.c);

```

Used:

```
var y = new [] {28943, 825, 11746, 16375, 32425, 19944, 21826, 15752, 15342, 3944, 28436}.Select(i=>new{v=i,c=Convert.ToString(i,2).Count(c=>c=='1')}).OrderByDescending(a=>a.c);
Console.WriteLine(y.Select(a => a.v.ToString()).Aggregate((s1,s2)=>s1+","+s2));

```

Result:

```
16375,15342,32425,28943,11746,19944,28436,15752,3944,825,21826

```

EDIT: .NetFiddle - http://dotnetfiddle.net/ahMMbq

# Answer
> 1 votes
Longwinded C#:

```
using System;

namespace P
{
    class P
    {
        static int T(int v) { int i = 0; while (v != 0) { i += (v & 1); v >>= 1; } return i; }
        static int[] S(int[] a)
        { Array.Sort<int>(a, (x, y) => { return (T(x) > T(y)) ? -1 : (T(x) < T(y)) ? 0 : 1; }); return a; }
        static void Main(string[] args)
        {
            foreach (var i in S(new int[]{ 28943, 825, 11746, 16375, 32425, 19944, 21826, 15752, 15342, 3944, 28436 }))
                Console.WriteLine("{0}\t{1}\t{2}", i, Convert.ToString(i, 2), T(i));
            Console.ReadKey();
        }
    }
}

```

# Answer
> 1 votes
**C# 95**

```
int[]o(int[]d){return d.OrderByDescending(v =>Convert.ToString(v,2).Sum(c =>c-'0')).ToArray();}

```

# Answer
> 1 votes
## PHP - 89 bytes

Here is the best I have been able to do so far.

```
function f($a){usort($a,function($a,$b){$c=gmp_popcount;return$c($a)<$c($b);});return$a;}

```

If I am allowed to sort the array in-place (which is idiomatic for PHP), then it is only 81:

```
function f(&$a){usort($a,function($a,$b){$c=gmp_popcount;return$c($a)<$c($b);});}

```

# Answer
> 1 votes
## Perl, 56 bytes

```
sub x{$_=sprintf'%b',@_;s/1//g}print sort{x($b)<=>x$a}<>

```

Input is expected in STDIN, one integer per line. Output is in descending order.

`sprintf '%b'` converts the number into binary representation. `s/1//` replaces the `1`, the return value is the number of replacements. Thus function `x` returns the number of `1` in the binary representation of the number. The sorting function sorts the number according to their binary 1's count. By exchanging `$a` and `$b` the sorting order is reversed to ascending.

# Answer
> 1 votes
# Japt, 7 bytes

```
ñ_¤è1Ãw

```

Test it

---

## Explanation

Implicit input of array `U`.

```
ñ_   Ã

```

Sort (`ñ`) by passing each element through a function.

```
¤

```

Convert to base 2 string.

```
è1

```

Count the number of `1`s.

```
w

```

Reverse and implicitly output the resulting array.

---

## Alternatives

```
ñ_¤o1Ãw
ñ_¤kTÃw

```

# Answer
> 1 votes
**Javascript** \- Lengthy but result is according to my expectation \- sorting numbers in ascending order according to number of binary 1s in them. If binary 1s are equal then sorting done on the base of decimal ascending order.

**Thumbs up if anybody can improve or give shorter solution in javascript**

```
  function sortNumberByBinary1s(numbers){
      //sort numbers first
      numbers=numbers.sort();
      console.log(numbers,'numbers');

      //2dimenstional array to store original number and its binary 1s
      var binNumArr = [];
      //loop to count binary 1s in each number
      for(i=0;i<numbers.length;i++){
        var num = numbers[i];
        // var binNum = Number(num.toString(2));

        let binary1 = 0;
        do if(num&1) binary1++;
        while(num>>=1);

        //store original number and its binary 1s in 2dimenstional array
        binNumArr[numbers[i]]={'number':numbers[i],'binary1':binary1};

      }

    //sort binNumArr (22dimenstional array by Number value)
    //filter(() => true) to remove empty values
      var byNumSortedArray=binNumArr.sort(function(a, b){return a.number - b.number}).filter(() => true);

      //sort byNumberSorted array by binary1 value
      var byBinary1SortedArray=byNumSortedArray.sort(function(a, b){return a.binary1 - b.binary1});

      console.log(byBinary1SortedArray,'byBinary1SortedArray');

    //get only sortedNumbers from array and return result
      var sortedNumbers=[]
      for(i=0;i<byBinary1SortedArray.length;i++){
        try{
          var number = byBinary1SortedArray[i].number;
        }catch(e){
          console.log(e,'error');
        }
        console.log(number,'number');
        sortedNumbers[i]=number;

      }
      console.log(sortedNumbers,'sortedNumbers array');
      return sortedNumbers;

    }

```

**Input: \[3,4,5,6,7,8\]**

```
  sortNumberByBinary1s([3,4,5,6,7,8]);

```
* {number: 4, binary1: 1}
* {number: 8, binary1: 1}
* {number: 3, binary1: 2}
* {number: 5, binary1: 2}
* {number: 6, binary1: 2}
* {number: 7, binary1: 3}

**Output: \[4, 8, 3, 5, 6, 7\]**

# Answer
> 1 votes
# Stax, 6 bytes

```
╖a☻║B⌡

```

Run and debug it at staxlang.xyz!

This will output the Unicode characters in a string. Add `$` at the end (or step through execution) to see decimal.

## Unpacked (7 bytes) and Explanation

```
{:B|+or
{          Begin block.
 :B          Convert to binary array. Ex: 11746 -> [1, 0, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0]
   |+        Sum.
     o     Terminate block and use it to sort array (ascending).
      r    Reverse. Implicit print.

```

Before descending order was specified in the question, there was a 6-byte unpacked solution. This is short enough that packing (into `ÇÄì¬♥#`) changed nothing:

```
{:B|+o

```

Run and debug it at staxlang.xyz!

# Answer
> 1 votes
# Haskell, ~~57~~ 54 bytes

<sup>-3 bytes thanks to Laikoni! (making the counting function pointfree by using the fact that we only need to support 32bit ints)</sup>

```
sortOn$sum.(mapM(pure[0,1])[1..32]!!)
import Data.List

```

Try it online!

## Explanation

The function call `sortOn f xs` returns `xs :: [x]` sorted by comparing `ys = map (f :: x -> y) xs` where the type `y` has to be an instance of `Ord`, so we just need to feed it a function that counts the number of 1-bits:

```
(sum . mapM (const [0,1]) [1..32] !!)

```

The expression `mapM (const [0,1]) [1..n]` generates all the sequences of `[0,1]` with length `n` (`n = 32` is sufficient since we only need to handle 32bit ints) in the right order, so we just need to index into these and take it's sum.

Example: `mapM (const [0,1]) [1..2] !! 1 ≡ [[0,0],[0,1],[1,0],[1,1]] !! 2 ≡ [0,1]`

# Answer
> 1 votes
# Kotlin, ~~57~~ 44 bytes

```
{it.sortedBy{-it.toString(2).sumBy{it-'0'}}}

```

Try it online!

# Answer
> 1 votes
# K (ngn/k), ~~11~~ 10 bytes

```
{x@>+/2\x}

```

Try it online!

# Answer
> 1 votes
# MathGolf, 5 bytes

```
á{âΣ~

```

Try it online!

### Explanation:

```
á{âΣ~
á{     Sort by the
    ~  Negative
   Σ   Digit sum
  â    Of the number converted to binary

```

# Answer
> 1 votes
# Powershell, ~~40~~ 45 bytes

```
$args|sort{for(;$_;$_=$_-shr1){$s+=$_%2}$s}-d

```

Explanation:

Sort all arguments from the predefined `$args` in a descendant order by sum of bits `$s`.

Note: The script uses `-shr1` instead `/2` because a Powershell does not provide integer `div`.

Test script:

```
$f = {

$args|sort{for(;$_;$_=$_-shr1){$s+=$_%2}$s}-d

}

&$f 0 1 3 4
&$f 16375 15342 32425 11746 28436 19944 28943 3944 15752 825 21826

```

Output:

```
3
0
4
1
16375
15342
32425
19944
28943
11746
28436
15752
3944
21826
825

```

# Answer
> 1 votes
# Factor, 31 bytes

```
[ [ bit-count ] inv-sort-with ]

```

Try it online!

# Answer
> 1 votes
# Rust, 36 bytes

```
|s|s.sort_by_key(|n|n.count_zeros())

```

Try it online!

Modifies the input slice in place. It works by sorting the array by the number of zeros. Another 36 byte solution:

```
|s|s.sort_by_key(|n|!n.count_ones())

```

Try it online!

This one sorts by the bitwise negation of the number of ones.

# Answer
> 1 votes
# Pyth, 12 bytes

```
o_/.BsN"1"cw

```

Try it online!

explanation:

```
               print(
o                sorted(
           w       input()
          c        .split()
                 , key = lambda N:
 _                 -
   .B              bin(
     s               int(
      N                N
                     )
                   )
  /                .count(
       "1"           "1"
                   )
                 )
               )

```

i'm aware there already is a Pyth answer, i just wanted to take a crack at it myself

# Answer
> 1 votes
# Vyxal, ~~6~~ 4 bytes

```
µb∑⌐

```

Try it Online!

### Explained

```
µb∑⌐
µ     # lambda
 b    # binary
  ∑   # sum (basically adds everything inside the binary, which is equivalent to the number of 1's
   ⌐  # reverse

```

# Answer
> 1 votes
# Zsh, 72 bytes

```
(for i;<<<${#${(M)${(s::)$((i<0?[##2]2**32+i:[##2]i))}#1}}\ $i)|sort -rn

```

Try it online!

# Answer
> 1 votes
# Thunno 2, 4 bytes

```
Þḃ1c

```

Attempt This Online!

**Alternatively:**

```
Þ2BS

```

Attempt This Online!

#### Explanation

```
Þḃ1c  # Implicit input
Þ     # Sort the input by the following:
 ḃ    #  Convert the number to binary
  1c  #  Count the number of 1s
      # Implicit output

```

```
Þ2BS  # Implicit input
Þ     # Sort the input by the following:
 2B   #  Convert the number to a binary list
   S  #  Sum the resulting list
      # Implicit output

```

# Answer
> 0 votes
# Jelly, 5 bytes

```
BS$ÞṚ

```

Try it online!

# Answer
> 0 votes
# PHP, 71

```
usort($a,function($a,$b){for(;$a&&$b;$a&=$a-1,$b&=$b-1);return$b-$a;});

```

If we assume there will be no dulicates, 69

```
foreach($a as$v)$b[$v]=gmp_popcount($v);arsort($b);$a=array_keys($b);

```

If we accept ascending sort, 68

```
foreach($a as$v)$b[$v]=gmp_popcount($v);asort($b);$a=array_keys($b);

```

That is, given `$a`. So, I'm unclear on whether we can assume the input, as various solutions go to various lengths to get it.

# Answer
> 0 votes
# Perl 5, 51 bytes

```
sub j{(sprintf'%b',@_)=~y/1//}say sort{j($b)-j$a}<>

```

Try it online!

# Answer
> 0 votes
# Pyth, ~~8~~ 6 bytes

```
_osjN2

```

Try it online!

##### Explanation

```
_osjN2  | Full code
_osjN2Q | with implicit variables
--------+------------------------
 o    Q | Sort the input by
   jN2  |  convert to binary list
  s     |  sum
_       | Reverse

```

# Answer
> 0 votes
# Python 2, 59 bytes

```
def f(l):l.sort(key=lambda x:`bin(x)`.count('1'),reverse=1)

```

Try it online!

# Answer
> 0 votes
# Pyt, 19 bytes

```
ĐĐ↑Ḷ⌊⁺ᴇĐ3ȘĦ*⇹↔+Ş⇹%Ɩ

```

Try it online!

### Explanation

```
                         Implicit input (as a list of integers)
ĐĐ                       Triplicate the list
  ↑                      Get the maximum value of the list (X_m)
   Ḷ⌊⁺ᴇĐ                 Push Y=10^(floor(log_10(X_m))+1) twice
        3Ș               Swap the top three elements on the list [puts the input on top]
          Ħ              Get the Hamming weight of each element of the input
           *             Multiply the Hamming weight by Y
            ⇹            Swap the top two elements on the stack
             ↔           Flip the stack [Puts the list on top, followed by Hamming weights multiplied by Y]
              +          Add the two lists element-wise [resulting in Z=[Z_0,Z_1,...]]
               Ş         Sort the resulting list in descending order
                ⇹        Swap the top two elements on the stack
                 %       Take Z mod Y
                  Ɩ      Convert Z mod Y to integers
                         Implicit print

```

This is as long as it is because Pyt doesn't allow sorting by anything other than the values in the array; this means that a workaround had to be devised to allow the proper sorting

# Answer
> 0 votes
# K (oK), 19 bytes

```
{t@>+/'(99#2)\'t:x}

```

Try it online!

# Answer
> 0 votes
# Dart, ~~102~~ ~~99~~ 84 bytes

```
F(a)=>'1'.allMatches(a.toRadixString(2)).length;f(List l)=>l.sort((a,b)=>F(a)-F(b));

```

Try it online!

- -3 bytes by using allMatches instead of replaceAll
- -15 bytes by using - instead of compareTo and replacing List\< int \> by List

# Answer
> 0 votes
# Perl 6, 36 bytes

```
@a.sort({sum .base(2).comb}).reverse

```

Try it online!

# Answer
> 0 votes
# APL(NARS), 27 chars, 54 bytes

```
{⍵[⍒{+/(2⍴⍨⌊1+2⍟1+⍵)⊤⍵}¨⍵]}

```

test

```
  f←{⍵[⍒{+/(2⍴⍨⌊1+2⍟1+⍵)⊤⍵}¨⍵]}
  f 825 32425 15342 11746 28943 28436 21826 16375 15752 19944 3944
16375 15342 32425 11746 28943 28436 19944 15752 3944 825 21826

```

# Answer
> 0 votes
# J-uby, 33 bytes

```
:sort_by+(:%&"%b"|~:count&?1|:-@)

```

Attempt This Online!

# Answer
> 0 votes
# Pyt, 16 bytes

```
ĐĦ⇹Đ↑⁺Đ3Ș⇹↔*+Ş⇹%

```

Try it online!

Pyt only allows for sorting on the values themselves, so a kludge had to be done.

```
Đ                     implicit input (v); Đuplicate
 Ħ                    get Ħamming weight of each element (H)
  ⇹Đ↑                 get maximum of input (m)
     ⁺                increment m
      Đ               Đuplicate m
       3Ș⇹↔           Stack manipulation
           *          multiply H by m+1
            +         Add v to H*(m+1)
             Ş        Şort in descending order
              ⇹%      modulo m+1; implicit print

```

# Answer
> 0 votes
# Thunno, \\$ 14 \log\_{256}(96) \approx \\$ 11.52 bytes

```
DebdiSEZZz;.AK

```

Attempt This Online!

Unfortunately Thunno lacks a "sort by" built-in.

#### Explanation

```
DebdiSEZZz;.AK  # Implicit input
De    E         # Duplicate and map:
  bd            #  Convert to binary
    iS          #  And sum the digits
       ZZ       # Zip with input
         z;     # Reverse-sort
           .AK  # Last element of each
                # Implicit output

```

---
Tags: code-golf, sorting, bitwise
---


# Question
Title: Find the number of n-by-n (-1, 0, 1) matrices with zero permanent as quickly as possible
The permanent of an \\$n\\$-by-\\$n\\$ matrix \\$A = (a\_{i,j})\\$ is defined as:

$$\operatorname{perm}(A)=\sum\_{\sigma\in S\_n}\prod\_{i=1}^n a\_{i,\sigma(i)}$$

For a fixed \\$n\\$, consider the \\$n\\$-by-\\$n\\$ matrices whose entries are taken from \\$\\{-1, 0, +1\\}\\$ .

## Task

For each \\$n\\$ from 1 upwards, output the number of \\$n\\$-by-\\$n\\$ \\$(-1, 0, 1)\\$ matrices with zero permanent.

The output format looks like this:

```
n = 1, 1
n = 2, 33
n = 3, 7555
n = 4, 13482049
n = 5, 186481694371
n = 6, ...

```

## Score

Your score is the largest \\$n\\$ your code gets to in 20 minutes in total on my computer, this is not 20 minutes per \\$n\\$.

If two entries get the same \\$n\\$ score, then the winning entry will be the one that gets to the highest \\$n\\$ in the shortest time on my machine. If the two best entries are equal on this criterion too then the winner will be the answer submitted first.

You are in no way allowed to hard-code solutions.

## Languages and libraries

You can use any freely available language and libraries you like. I must be able to run your code so please include a full explanation for how to run/compile your code in windows if at all possible.

## My Machine

The timings will be run on my machine, Intel Core i7-9750H 6 cores, 12 threads, The machine runs Windows 10.

## Updated

Brute forcing every matrix (of which there are \\$3^{n^2}\\$) is not necessarily a particularly good answer, especially since there are many symmetries that preserve the value of the permanent. Thanks for @isaacg.

# Answer
> 13 votes
# Rust, \\$A(5) = 186481694371\\$ in 0.2 s, \\$A(6) = 19733690332538577\\$ in 580 s

(Unofficial times on a Core i7-10710U with 6 cores/12 threads.)

### `src/main.rs`

```
use itertools::Itertools;
use num_integer::gcd;
use rayon::prelude::*;
use std::cmp::Ordering;
use std::collections::HashMap;
use std::convert::TryFrom;
use std::sync::Mutex;

type Count = u64;
type Coeff = i32;

fn sort_scols(n: u32, i: u32, sets: &[u32], state: &[Coeff]) -> Vec<u32> {
    let mut scol_ranks: Vec<u32> = (0..2 * n).map(|scol| (scol >> 1 > i) as u32).collect();
    let mut sorted_scols: Vec<u32> = (0..2 * n).collect();
    let mut scol_descs = vec![vec![]; 2 * n as usize];
    for (set_index, (&set, &coeff)) in sets.iter().zip(state).enumerate() {
        if coeff != 0 {
            for col in 0..n {
                if set & 1 << col != 0 {
                    scol_descs[(col as usize) << 1].push(set_index);
                    scol_descs[(col as usize) << 1 | 1].push(set_index);
                }
            }
        }
    }
    let mut sorted_set_indexes: Vec<_> = (0..sets.len()).collect();
    let mut set_ranks: Vec<u32> = vec![!0; sets.len()];
    let mut set_descs = vec![(0, vec![]); sets.len()];

    while {
        for (&coeff, set_desc) in state.iter().zip(&mut set_descs) {
            set_desc.0 = coeff;
            set_desc.1.clear();
        }
        let mut seen = 0;
        for &scol in &sorted_scols {
            if seen & 1 << (scol >> 1) == 0 {
                seen |= 1 << (scol >> 1);
                if scol & 1 == 0 {
                    for (&set, set_desc) in sets.iter().zip(&mut set_descs) {
                        if set_desc.0 != 0 && set & 1 << (scol >> 1) != 0 {
                            set_desc.1.push(scol_ranks[scol as usize]);
                        }
                    }
                } else {
                    for (&set, set_desc) in sets.iter().zip(&mut set_descs) {
                        if set_desc.0 != 0 && set & 1 << (scol >> 1) != 0 {
                            set_desc.0 = -set_desc.0;
                            set_desc.1.push(scol_ranks[scol as usize]);
                        }
                    }
                }
            }
        }

        let set_index_key =
            |&set_index: &usize| (set_descs[set_index].0.abs(), &set_descs[set_index].1);
        sorted_set_indexes.sort_by_key(set_index_key);
        if sets.len() != 0 {
            let mut next_set_rank = 0;
            set_ranks[sorted_set_indexes[0]] = next_set_rank;
            for (&set_index0, &set_index1) in sorted_set_indexes.iter().tuple_windows() {
                if set_index_key(&set_index0) < set_index_key(&set_index1) {
                    next_set_rank += 1;
                }
                set_ranks[set_index1] = next_set_rank;
            }
        }

        let scol_set_index_key = |scol: u32| {
            let sign = 1 - 2 * (scol & 1) as Coeff;
            let set_ranks = &set_ranks[..];
            let set_descs = &set_descs[..];
            move |&set_index: &usize| (set_ranks[set_index], set_descs[set_index].0 * sign)
        };
        for (scol, scol_desc) in scol_descs.iter_mut().enumerate() {
            scol_desc.sort_by_key(scol_set_index_key(scol as u32));
        }
        let scol_cmp = |&scol0: &u32, &scol1: &u32| {
            scol_ranks[scol0 as usize]
                .cmp(&scol_ranks[scol1 as usize])
                .then_with(|| {
                    scol_descs[scol0 as usize]
                        .iter()
                        .map(scol_set_index_key(scol0))
                        .cmp(
                            scol_descs[scol1 as usize]
                                .iter()
                                .map(scol_set_index_key(scol1)),
                        )
                })
        };
        sorted_scols.sort_by(scol_cmp);

        let mut new_scol_ranks = vec![!0; 2 * n as usize];
        let mut next_rank = 0;
        let mut changed = false;
        new_scol_ranks[sorted_scols[0] as usize] = next_rank;
        for (&scol0, &scol1) in sorted_scols.iter().tuple_windows() {
            if scol_ranks[scol0 as usize] < scol_ranks[scol1 as usize] {
                next_rank += 1;
            } else if scol_cmp(&scol0, &scol1) == Ordering::Less {
                changed = true;
                next_rank += 1;
            }
            new_scol_ranks[scol1 as usize] = next_rank;
        }
        scol_ranks = new_scol_ranks;

        changed
    } {}

    let mut seen = 0;
    sorted_scols.retain(|scol| {
        seen & 1 << (scol >> 1) == 0 && {
            seen |= 1 << (scol >> 1);
            true
        }
    });
    assert_eq!(seen, !(!0 << n));

    sorted_scols
}

fn count(n: u32) -> Count {
    static ERR: &str = "n is too large";
    Count::checked_pow(3, TryFrom::try_from(n * n).expect(ERR)).expect(ERR);
    (1..=Coeff::try_from(n).expect(ERR)).fold(1, |x: Coeff, y| x.checked_mul(y).expect(ERR));

    let mut cur_sets = vec![0];
    let mut cur_set_indexes = vec![0];

    let mut cur_states = HashMap::new();
    cur_states.insert(vec![1], 1);

    for k in 0..n {
        for i in 0..n {
            let keep_set = |&set: &u32| {
                if set.count_ones() == k {
                    !set & !1 << i & !(!0 << n) != 0
                } else {
                    set & 1 << i == 0
                }
            };
            let enlarge_set = |&set: &u32| set.count_ones() == k && set & 1 << i == 0;
            let new_sets: Vec<u32> = cur_sets
                .iter()
                .copied()
                .filter(keep_set)
                .chain(
                    cur_sets
                        .iter()
                        .copied()
                        .filter(enlarge_set)
                        .map(|set| set | 1 << i),
                )
                .collect();
            let mut new_set_indexes = vec![!0; 1 << n];
            for (set_index, &set) in new_sets.iter().enumerate() {
                new_set_indexes[set as usize] = set_index;
            }

            let new_states = Mutex::new(HashMap::new());
            cur_states.into_par_iter().for_each(|(cur_state, count)| {
                for elt in -1..=1 {
                    let mut new_state: Vec<Coeff> = cur_sets
                        .iter()
                        .copied()
                        .zip(&cur_state)
                        .filter(|(set, _)| keep_set(set))
                        .map(|(_, &coeff)| coeff)
                        .chain(
                            cur_sets
                                .iter()
                                .copied()
                                .zip(&cur_state)
                                .filter(|(set, _)| enlarge_set(set))
                                .map(|(set, &coeff)| {
                                    let mut new_coeff = coeff * elt;
                                    if set & !(!0 << i) != 0 {
                                        new_coeff +=
                                            cur_state[cur_set_indexes[set as usize | 1 << i]];
                                    }
                                    new_coeff
                                }),
                        )
                        .collect();

                    let factor = new_state.iter().copied().fold(0, gcd);
                    if factor > 1 {
                        for coeff in &mut new_state {
                            *coeff /= factor;
                        }
                    }

                    let sorted_scols = sort_scols(n, i, &new_sets, &new_state);

                    let new_state: Vec<Coeff> = new_sets
                        .iter()
                        .map(|&set| {
                            let mut permuted_set = 0;
                            let mut sign = 0;
                            for (col, &permuted_scol) in sorted_scols.iter().enumerate() {
                                sign ^= set >> col & permuted_scol & 1;
                                permuted_set |= (set >> col & 1) << (permuted_scol >> 1);
                            }
                            (1 - 2 * sign as Coeff)
                                * new_state[new_set_indexes[permuted_set as usize] as usize]
                        })
                        .collect();

                    *new_states.lock().unwrap().entry(new_state).or_insert(0) += count;
                }
            });

            cur_sets = new_sets;
            cur_set_indexes = new_set_indexes;
            cur_states = new_states.into_inner().unwrap();
        }
    }

    *cur_states.get(&vec![0]).unwrap_or(&0)
}

fn main() {
    for n in 1..=6 {
        println!("{} {}", n, count(n));
    }
}

```

### `Cargo.toml`

```
[package]
name = "permanent"
version = "0.1.0"
authors = ["Anders Kaseorg <andersk@mit.edu>"]
edition = "2018"

[dependencies]
num-integer = "0.1.41"
rayon = "1.2.1"
itertools = "0.8.2"

```

### Building and running

```
$ cargo build --release
$ time target/release/permanent
1 1
2 33
3 7555
4 13482049
5 186481694371
6 19733690332538577
5995.30user 282.67system 9:42.97elapsed 1076%CPU (0avgtext+0avgdata 6479028maxresident)k
0inputs+0outputs (0major+3259222minor)pagefaults 0swaps

```

### How it works

This counts matrices using dynamic programming so we don’t need to enumerate all of them directly. Basically, the state of a partially filled matrix is represented by the coefficients of an expression for the permanent as a polynomial in the remaining unfilled elements. Specifically, it corresponds to a partial execution of the following algorithm for calculating the permanent:

\\$\operatorname{perm} A = c\_{\\{0, 1, \dotsc, n - 1\\}}\\$, where \\$c\_\varnothing = 1\\$, \\$c\_S = \sum\_{i \in S} c\_{S \smallsetminus \\{i\\}}a\_{|S| - 1, i}\\$ for \\$S \ne \varnothing\\$.

For example, here’s the \\$n = 4\\$ calculation written out explicitly:

```
c = 1

c0 = c * a00
c1 = c * a01
c2 = c * a02
c3 = c * a03

c01  = c1 * a10; c02  = c2 * a10; c03  = c3 * a10
c01 += c0 * a11; c12  = c2 * a11; c13  = c3 * a11
c02 += c0 * a12; c12 += c1 * a12; c23  = c3 * a12
c03 += c0 * a13; c13 += c1 * a13; c23 += c2 * a13

c012  = c12 * a20; c013  = c13 * a20; c023  = c23 * a20
c012 += c02 * a21; c013 += c03 * a21; c123  = c23 * a21
c012 += c01 * a22; c023 += c03 * a22; c123 += c13 * a22
c013 += c01 * a23; c023 += c02 * a23; c123 += c12 * a23

c0123  = c123 * a30
c0123 += c023 * a31
c0123 += c013 * a32
c0123 += c012 * a33

return c0123

```

After executing each line, we can forget the filled elements `a…` and represent the current state with just the `c…` variables that are still live. This representation collapses many different partially filled matrices into the same coefficient vector. For example, swapping any two filled rows results in the same coefficient vector.

The `sort_scols` function further collapses the state space by using the symmetries of column permutations and column sign flipping to try to find a canonical representation for each state. It doesn’t do a perfect job, but this imperfection only impacts performance, not correctness.

# Answer
> 10 votes
## C# (\\$\textrm{A330134}(5)=186481694371\\$ in under 10 seconds)

```
using System;
using System.Collections.Generic;
using System.Linq;
using System.Numerics;

namespace Sandbox
{
    // See https://codegolf.stackexchange.com/q/196712
    static class Permanent
    {
        const int numThreads = 12;

        static void Main(string[] args)
        {
            var sw = new System.Diagnostics.Stopwatch();
            sw.Start();
            for (int n = 1; n < 8; n++)
            {
                Console.WriteLine($"{n}\t{_PPCG196712_LaplaceMT(n)}\t{sw.ElapsedMilliseconds}ms");
            }
        }

        internal static BigInteger _PPCG196712_LaplaceMT(int n)
        {
            // If we have a zero row then the permanent is zero.
            // If the first zero row is number i then the previous i rows have (3^n)-1 possibilities each, and the remaining ones have 3^n.
            BigInteger result = 0;
            int threePowN = (int)BigInteger.Pow(3, n);
            for (int i = 0; i < n; i++)
            {
                result += BigInteger.Pow(threePowN - 1, i) * BigInteger.Pow(threePowN, n - i - 1);
            }

            // Let's call a row containing a permutation of 1^1 0^{n-1} a "singleton row".
            // Under Laplace expansion it simplifies to a single {n-1}x{n-1} permanent.
            // If we have two singleton rows with the same non-zero index, that {n-1}x{n-1} permanent has a zero row, so the nxn permanent must be zero.
            // If we have multiple distinct singleton rows, we still need to worry about double-counting.
            // But all this effort would give roughly a 1.5% improvement at n=6, so is probably not worth it.

            // Now the interesting rows. We cluster similar rows as a technique to optimise column permutations.
            var clusters = new List<Cluster>();
            for (int ones = 1; ones <= n; ones++)
                for (int negs = 0; negs <= ones && ones + negs <= n; negs++)
                    clusters.Add(new Cluster(n, ones, negs));

            // Consider partitions of n-1 by cluster.
            foreach (var partition in PartitionAssignments(clusters, n-1))
            {
                var subclusters = partition.OrderBy(tuple =>
                {
                    var (cluster, k) = tuple;
                    // What's the speedup factor of pivoting on this cluster?
                    return k < cluster.DistinctCounts.Count ? cluster.DistinctCounts[k] / (double)cluster.NaiveCounts[k] : 1;
                }).ToList();

                // We pivot on the first cluster, and take a Cartesian product.
                result += Enumerable.Range(0, numThreads).AsParallel().
                    Select(threadId => CountByPartition(n, subclusters, 0, new sbyte[n - 1][], 0, 1, threadId)).
                    Aggregate(BigInteger.Zero, (a, b) => a + b);
            }

            return result;
        }

        private static BigInteger CountByPartition(int n, IReadOnlyList<(Cluster cluster, int repeat)> clusters, int clusterIdx, sbyte[][] matrix, int rowIdx, BigInteger weight, int threadId)
        {
            if (clusterIdx == clusters.Count) return weight * Count_Laplace(matrix) << (n - 1);

            int k = clusters[clusterIdx].repeat;
            if (clusterIdx == 0 && clusters[0].repeat < clusters[0].cluster.DistinctCounts.Count)
            {
                // Pivot
                weight *= Binom(n - 1, k) * Factorial(n - 1 - k); // Choose the pivoted rows and then permute the others freely

                BigInteger sum = 0;
                var reps = clusters[0].cluster.Representatives[k];

                int delta = reps.Count >= numThreads || clusterIdx == clusters.Count - 1 ? numThreads : 1;
                int skip = delta == 1 ? 0 : threadId;

                for (int repIdx = skip; repIdx < reps.Count; repIdx += delta)
                {
                    var (prefixWeight, prefix) = reps[repIdx];
                    for (int i = 0; i < k; i++) matrix[rowIdx + i] = prefix[i];
                    sum += CountByPartition(n, clusters, clusterIdx + 1, matrix, rowIdx + k, weight * prefixWeight, delta == 1 ? threadId : -1);
                }
                return sum;
            }

            {
                if (clusterIdx == 0) weight = Factorial(n - 1); // Permute all rows freely

                var rows = clusters[clusterIdx].cluster.Rows;
                var indices = new int[k];
                BigInteger sum = 0;

                int skip = threadId > 0 ? threadId : 0;
                int delta = threadId >= 0 ? numThreads : 1;

                while (true)
                {
                    if (skip == 0)
                    {
                        for (int i = 0; i < k; i++)
                        {
                            var j = indices[i];
                            var inRow = rows[j];
                            matrix[rowIdx + i] = inRow;
                        }

                        // Adjust the weight to account for duplicates in this cluster.
                        var recurWeight = weight;
                        int currRun = 1;
                        for (int i = 1; i < k; i++)
                        {
                            if (indices[i] == indices[i - 1]) currRun++;
                            else { recurWeight /= Factorial(currRun); currRun = 1; }
                        }
                        recurWeight /= Factorial(currRun);

                        sum += CountByPartition(n, clusters, clusterIdx + 1, matrix, rowIdx + k, recurWeight, -1);
                    }

                    skip--;
                    if (skip < 0) skip += delta;

                    if (indices[0] == rows.Count - 1) break;
                    NextOrderedMultiset(indices, rows.Count);
                }

                return sum;
            }
        }

        private static IEnumerable<IReadOnlyList<(T, int)>> PartitionAssignments<T>(IReadOnlyList<T> elts, int n)
        {
            IEnumerable<IReadOnlyList<(T, int)>> Inner(int m, int maxPart, int off, List<(T, int)> prefix, ISet<int> indicesUsed)
            {
                if (m == 0)
                {
                    yield return new List<(T, int)>(prefix);
                    yield break;
                }

                for (int part = Math.Min(m, maxPart); part > 0; part--)
                {
                    // When we reduce the part, we re-enable skipped elts.
                    for (int i = part == maxPart ? off : 0; i < elts.Count; i++)
                    {
                        if (indicesUsed.Contains(i)) continue;

                        prefix.Add((elts[i], part));
                        indicesUsed.Add(i);

                        foreach (var soln in Inner(m - part, part, i + 1, prefix, indicesUsed)) yield return soln;

                        indicesUsed.Remove(i);
                        prefix.RemoveAt(prefix.Count - 1);
                    }
                }
            }

            return Inner(n, n, 0, new List<(T, int)>(), new HashSet<int>());
        }

        private static void NextOrderedMultiset(int[] indices, int @base)
        {
            int j = indices.Length - 1;
            while (indices[j] == @base - 1) j--;
            indices[j]++;
            j++;
            while (j < indices.Length) { indices[j] = indices[j - 1]; j++; }
        }

        private static BigInteger Count_Laplace(sbyte[][] matrix)
        {
            int m = matrix.Length;
            int n = m + 1;
            BigInteger[] sums = new BigInteger[m];
            uint gray = 0;
            int sign = 1;
            BigInteger[] weights = new BigInteger[n];
            for (uint i = 0; i < 1u << n; i++)
            {
                BigInteger term = 1;
                foreach (var sum in sums) term *= sum;

                for (int j = 0; j < n; j++)
                {
                    if (((gray >> j) & 1) == 1) weights[j] += sign * term;
                }

                // Gray code update
                int flipPos = (i + 1).CountTrailingZeros();
                if (flipPos == n) break;

                uint bit = 1u << flipPos;
                if ((gray & bit) == bit)
                {
                    for (int j = 0; j < m; j++) sums[j] -= matrix[j][flipPos];
                }
                else
                {
                    for (int j = 0; j < m; j++) sums[j] += matrix[j][flipPos];
                }
                gray ^= bit;
                sign = -sign;
            }

            // Count weighted subsets which total zero, optimising with meet-in-the-middle
            var distribL = SubsetSums(weights, 0, n >> 1);
            var distribR = SubsetSums(weights, n >> 1, n - (n >> 1));
            BigInteger total = -1; // Discount the zero column solution
            foreach (var kvp in distribL)
            {
                if (distribR.TryGetValue(-kvp.Key, out var v2)) total += kvp.Value * v2;
            }

            return total;
        }

        private static Dictionary<BigInteger, BigInteger> SubsetSums(BigInteger[] weights, int off, int len)
        {
            var distrib = new Dictionary<BigInteger, BigInteger> { [0] = 1 };
            for (int i = 0; i < len; i++)
            {
                var weight = weights[off + i];
                var nextDistrib = new Dictionary<BigInteger, BigInteger>(distrib);
                foreach (var kvp in distrib)
                {
                    nextDistrib.TryGetValue(kvp.Key - weight, out var tmp);
                    nextDistrib[kvp.Key - weight] = tmp + kvp.Value;

                    nextDistrib.TryGetValue(kvp.Key + weight, out tmp);
                    nextDistrib[kvp.Key + weight] = tmp + kvp.Value;
                }

                distrib = nextDistrib;
            }

            return distrib;
        }

        class Cluster
        {
            internal readonly IReadOnlyList<sbyte[]> Rows;

            internal readonly IReadOnlyList<int> NaiveCounts;
            internal readonly IReadOnlyList<int> DistinctCounts;
            internal readonly IReadOnlyList<IReadOnlyList<(int weight, IReadOnlyList<sbyte[]> prefix)>> Representatives;

            internal Cluster(int n, int ones, int negs)
            {
                if (ones == 0) throw new ArgumentOutOfRangeException(nameof(ones));
                if (negs > ones) throw new ArgumentOutOfRangeException(nameof(negs));

                Rows = BuildRows(n, ones, negs);

                // Build pairs and triples, and calculate their advantage factors.
                var naiveCounts = new List<int> { 1, Rows.Count };
                var distinctCounts = new List<int> { 1, 1 };
                var representatives = new List<IReadOnlyList<(int, IReadOnlyList<sbyte[]>)>>
                {
                    new List<(int, IReadOnlyList<sbyte[]>)>{ (1, new List<sbyte[]>()) },
                    new List<(int, IReadOnlyList<sbyte[]>)>{ (Rows.Count, new List<sbyte[]> { Rows.First() }) }
                };

                for (int k = 2; k < 4; k++)
                {
                    var counts = new Dictionary<BigInteger, int>();
                    var reps = new Dictionary<BigInteger, IReadOnlyList<sbyte[]>>();
                    int uncollapsed = 0;

                    var indices = new int[k];
                    while (true)
                    {
                        var subset = new sbyte[k][];
                        for (int i = 0; i < k; i++) subset[i] = Rows[indices[i]];

                        BigInteger count = Factorial(k);
                        int currRun = 1;
                        for (int i = 1; i < k; i++)
                        {
                            if (indices[i] == indices[i - 1]) currRun++;
                            else { count /= Factorial(currRun); currRun = 1; }
                        }
                        count /= Factorial(currRun);

                        uncollapsed += (int)count;
                        var encoding = CanonicalEncoding(subset);
                        counts.TryGetValue(encoding, out var oldCount);
                        counts[encoding] = oldCount + (int)count;
                        if (oldCount == 0) reps[encoding] = (sbyte[][])subset.Clone();

                        if (indices[0] == Rows.Count - 1) break;
                        NextOrderedMultiset(indices, Rows.Count);
                    }

                    naiveCounts.Add(uncollapsed);
                    distinctCounts.Add(reps.Count);
                    representatives.Add(counts.Select(kvp => (kvp.Value, reps[kvp.Key])).ToList());
                }

                NaiveCounts = naiveCounts;
                DistinctCounts = distinctCounts;
                Representatives = representatives;
            }

            private static List<sbyte[]> BuildRows(int n, int ones, int negs)
            {
                var rows = new List<sbyte[]>();
                void Append(sbyte[] row)
                {
                    // Ensure that we don't have both a row and its negative by testing canonicity.
                    if (ones > negs || Array.IndexOf(row, (sbyte)1) < Array.IndexOf(row, (sbyte)-1)) rows.Add((sbyte[])row.Clone());
                }

                var perm = new sbyte[n];
                for (int i = 0; i < negs; i++) perm[i] = -1;
                for (int i = n - ones; i < n; i++) perm[i] = 1;

                while (true)
                {
                    Append(perm);

                    // Next permutation
                    int k;
                    for (k = n - 2; k >= 0; k--)
                    {
                        if (perm[k] < perm[k + 1]) break;
                    }
                    if (k == -1) return rows;

                    int l;
                    for (l = n - 1; l > k; l--)
                    {
                        if (perm[k] < perm[l]) break;
                    }

                    var tmp = perm[k]; perm[k] = perm[l]; perm[l] = tmp;

                    for (int i = k + 1, j = n - 1; i < j; i++, j--)
                    {
                        tmp = perm[i]; perm[i] = perm[j]; perm[j] = tmp;
                    }
                }
            }

            private static BigInteger CanonicalEncoding(sbyte[][] rows)
            {
                return rows.Permutations().Select(_CanonicalEncodingInner).Min();
            }

            private static BigInteger _CanonicalEncodingInner(sbyte[][] rows)
            {
                BigInteger @base = BigInteger.Pow(3, rows.Length);
                BigInteger[] digits = new BigInteger[rows[0].Length];
                for (int i = 0; i < digits.Length; i++)
                {
                    for (int j = 0; j < rows.Length; j++)
                    {
                        digits[i] = digits[i] * 3 + rows[j][i] + 1;
                    }
                }
                return digits.OrderBy(x => x).Aggregate(BigInteger.Zero, (accum, digit) => accum * @base + digit);
            }
        }

        private static readonly int[] _DeBruijn32 = new int[]
        {
            0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8,
            31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
        };

        // Returns 32 for input 0.
        public static int CountTrailingZeros(this uint i)
        {
            if (i == 0) return 32;

            int j = (int)i;
            i = (uint)(j & -j);
            var idx = (i * 0x077CB531U) >> 27;
            return _DeBruijn32[idx];
        }

        public static IEnumerable<T[]> Permutations<T>(this IEnumerable<T> elts)
        {
            T[] arr = elts.ToArray();
            if (arr.Length == 0)
            {
                yield return arr;
                yield break;
            }

            int[] indices = Enumerable.Range(0, arr.Length).ToArray();
            while (true)
            {
                yield return arr.ToArray();
                // Next permutation
                int i = indices.Length - 1;
                while (i > 0 && indices[i - 1] > indices[i]) i--;

                if (i == 0) yield break;

                int j = indices.Length - 1;
                while (indices[j] < indices[i - 1]) j--;

                _DoubleSwap(arr, indices, i - 1, j);
                for (j = indices.Length - 1; i < j; i++, j--) _DoubleSwap(arr, indices, i, j);
            }
        }

        private static void _DoubleSwap<T>(T[] elts, int[] indices, int i, int j)
        {
            var t1 = elts[i];
            elts[i] = elts[j];
            elts[j] = t1;

            var t2 = indices[i];
            indices[i] = indices[j];
            indices[j] = t2;
        }

        private static BigInteger Factorial(int n) => n < 2 ? BigInteger.One : n * Factorial(n - 1);

        private static BigInteger Binom(int n, int k)
        {
            BigInteger result = 1;
            for (int i = 0; i < k; i++) result = result * (n - i) / (i + 1);
            return result;
        }
    }
}

```

Online demo

This employs the following tricks:

* If there's a zero row, the permanent is zero. These can be counted very fast, and then we can assume there's no zero row.
* Multiplying a row by \\$-1\\$ inverts the sign of the permanent. So we can assume a canonical sign for each row and then multiply by \\$2^n\\$.
* Permuting the rows leaves the permanent unchanged, so we can assume a canonical permutation of the rows and then multiply by a suitable factor.
* The permanent can be computed in better-than-brute-force time using Ryser's formula with Gray code enumeration of subsets of columns.
* Laplace expansion of the last row turns a factor of \\$\frac{3^n - 1}{2}\\$ into an instance of the subset sum problem, which can be tackled using dynamic programming with meet-in-the-middle.
* We can also permute columns, which is what `Cluster` is for. I think I've pushed the `Cluster` approach about as far as it can go, but I would like to find an efficient way of replacing it, because if we take the first row `[1, 1, 0, -1, -1, -1]` (with weight 60) then it would be nice to exploit the symmetry of the first two columns and the last three columns in the next cluster. The problem is that doing this naïvely adds a factor of \\$n!\\$, which is more expensive than the saving.
* The permutations are independent, so after a bit of pre-processing we have an embarrassingly parallel problem.

I compiled with VS2017 Community targetting .Net Framework 4.7.1 and compiled for "Release" with default settings. You may prefer to use .Net Core.

\\$n=6\\$ is still technically out of range - I calculated it in just under 3 hours on a 4-core AMD with `numThreads = 8`.

# Answer
> 0 votes
# Wolfram Language(Mathematica), \\$\textrm{A330134}(3)=7555\\$ in under 3 seconds

Naive brute force. So slow.

Try it online!

```
ClearAll[zeroPermanentMatricesCount]
zeroPermanentMatricesCount[n_] :=
  Module[{allMatrices},
    (* Generate all n x n matrices with entries -1, 0, 1 *)
    allMatrices = Tuples[Tuples[{-1, 0, 1}, n], n];

    (* Count matrices with zero permanent *)
    Count[allMatrices, m_ /; Permanent[m] == 0]
  ]
Do[Print["n = ", n, ", ", zeroPermanentMatricesCount[n]], {n, 1, 3}]

```

---
Tags: math, matrix, fastest-code
---


# Question
Title: Compute OEIS A161169, approximately and quickly
\\$T(n, k)\\$ gives the number of permutations of length \\$n\\$ with up to \\$k\\$ inversions. This values grows very quickly, for example for \\$T(20, 100) = 1551417550117463564\\$.

The maximum number of inversions possible is \\$n\frac{n-1}{2}\\$ so for \\$k = n\frac{n-1}{2}\\$ we know that \\$T(n, k) = n!\\$.

To make this task more interesting, and to allow for a wider variety of possible answers you will only have to compute \\$T(n, k)\\$ approximately.

# Examples:

For \\$n = 3\\$ and \\$k\\$ from \\$0…3\\$:

```
0.167, 0.5, 0.833, 1.0

```

For \\$n = 4\\$ and \\$k\\$ from \\$0…6\\$:

```
0.042, 0.167, 0.375, 0.625, 0.833, 0.958, 1.0

```

For \\$n = 5\\$ and \\$k\\$ from \\$0…10\\$:

```
0.008, 0.042, 0.117, 0.242, 0.408, 0.592, 0.758, 0.883, 0.958, 0.992, 1.0

```

For \\$n = 50\\$ and \\$k\\$ from \\$0…1225\\$:

```
0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.001, 0.001, 0.001, 0.001, 0.001, 0.001, 0.001, 0.001, 0.001, 0.001, 0.001, 0.001, 0.001, 0.001, 0.001, 0.001, 0.001, 0.001, 0.002, 0.002, 0.002, 0.002, 0.002, 0.002, 0.002, 0.002, 0.002, 0.003, 0.003, 0.003, 0.003, 0.003, 0.003, 0.003, 0.004, 0.004, 0.004, 0.004, 0.005, 0.005, 0.005, 0.005, 0.006, 0.006, 0.006, 0.006, 0.007, 0.007, 0.007, 0.008, 0.008, 0.008, 0.009, 0.009, 0.01, 0.01, 0.011, 0.011, 0.012, 0.012, 0.013, 0.013, 0.014, 0.015, 0.015, 0.016, 0.017, 0.017, 0.018, 0.019, 0.02, 0.02, 0.021, 0.022, 0.023, 0.024, 0.025, 0.026, 0.027, 0.028, 0.029, 0.03, 0.032, 0.033, 0.034, 0.035, 0.037, 0.038, 0.039, 0.041, 0.042, 0.044, 0.046, 0.047, 0.049, 0.051, 0.052, 0.054, 0.056, 0.058, 0.06, 0.062, 0.064, 0.066, 0.069, 0.071, 0.073, 0.075, 0.078, 0.08, 0.083, 0.085, 0.088, 0.091, 0.094, 0.096, 0.099, 0.102, 0.105, 0.108, 0.112, 0.115, 0.118, 0.121, 0.125, 0.128, 0.132, 0.136, 0.139, 0.143, 0.147, 0.151, 0.155, 0.159, 0.163, 0.167, 0.171, 0.175, 0.18, 0.184, 0.189, 0.193, 0.198, 0.202, 0.207, 0.212, 0.217, 0.222, 0.227, 0.232, 0.237, 0.242, 0.247, 0.253, 0.258, 0.263, 0.269, 0.274, 0.28, 0.286, 0.291, 0.297, 0.303, 0.309, 0.315, 0.321, 0.327, 0.333, 0.339, 0.345, 0.351, 0.357, 0.363, 0.37, 0.376, 0.382, 0.389, 0.395, 0.401, 0.408, 0.414, 0.421, 0.427, 0.434, 0.44, 0.447, 0.454, 0.46, 0.467, 0.473, 0.48, 0.487, 0.493, 0.5, 0.507, 0.513, 0.52, 0.527, 0.533, 0.54, 0.546, 0.553, 0.56, 0.566, 0.573, 0.579, 0.586, 0.592, 0.599, 0.605, 0.611, 0.618, 0.624, 0.63, 0.637, 0.643, 0.649, 0.655, 0.661, 0.667, 0.673, 0.679, 0.685, 0.691, 0.697, 0.703, 0.709, 0.714, 0.72, 0.726, 0.731, 0.737, 0.742, 0.747, 0.753, 0.758, 0.763, 0.768, 0.773, 0.778, 0.783, 0.788, 0.793, 0.798, 0.802, 0.807, 0.811, 0.816, 0.82, 0.825, 0.829, 0.833, 0.837, 0.841, 0.845, 0.849, 0.853, 0.857, 0.861, 0.864, 0.868, 0.872, 0.875, 0.879, 0.882, 0.885, 0.888, 0.892, 0.895, 0.898, 0.901, 0.904, 0.906, 0.909, 0.912, 0.915, 0.917, 0.92, 0.922, 0.925, 0.927, 0.929, 0.931, 0.934, 0.936, 0.938, 0.94, 0.942, 0.944, 0.946, 0.948, 0.949, 0.951, 0.953, 0.954, 0.956, 0.958, 0.959, 0.961, 0.962, 0.963, 0.965, 0.966, 0.967, 0.968, 0.97, 0.971, 0.972, 0.973, 0.974, 0.975, 0.976, 0.977, 0.978, 0.979, 0.98, 0.98, 0.981, 0.982, 0.983, 0.983, 0.984, 0.985, 0.985, 0.986, 0.987, 0.987, 0.988, 0.988, 0.989, 0.989, 0.99, 0.99, 0.991, 0.991, 0.992, 0.992, 0.992, 0.993, 0.993, 0.993, 0.994, 0.994, 0.994, 0.994, 0.995, 0.995, 0.995, 0.995, 0.996, 0.996, 0.996, 0.996, 0.997, 0.997, 0.997, 0.997, 0.997, 0.997, 0.997, 0.998, 0.998, 0.998, 0.998, 0.998, 0.998, 0.998, 0.998, 0.998, 0.999, 0.999, 0.999, 0.999, 0.999, 0.999, 0.999, 0.999, 0.999, 0.999, 0.999, 0.999, 0.999, 0.999, 0.999, 0.999, 0.999, 0.999, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0

```

# Input:

One value: \\$n\\$.

# Output:

\\$\frac{T(n,\lfloor n^2/4 \rfloor)}{n!}\\$ rounded to three decimal places. \\$T(n, k)\\$ is defined by OEIS sequence A161169.

# Sample input and output

```
n = 3. Output: 0.833
n = 6. Output: 0.765
n = 9. Output: 0.694
n = 12. Output: 0.681
n = 15. Output: 0.651
n = 18. Output: 0.646
n = 50. Output: 0.586
n = 100. Output: 0.56
n = 150. Output: 0.549
n = 200. Output: 0.542
n = 250. Output: 0.538
n = 300. Output: 0.535

```

Your code should be correct no matter what values of \\$n\\$ and \\$k\\$ are given but will only be tested on \\$k = \lfloor n^2/4 \rfloor \\$. Your output must be within \\$0.001\\$ of the correct value.

# Score

I will run your code on my machine: 8GB RAM, AMD FX(tm)-8350 Eight-Core Processor running Ubuntu 16.04.6 LTS.

I will test for \\$n = 50, 100, 150, 200, 250, 300, 350, 400, ...\\$ until it no longer completes in 10 seconds. I will also limit the RAM used to 6GB using https://github.com/pshved/timeout.

Your score is the highest \\$n\\$ your code can reach on my computer within the time limit. If there is a tie, the first answer wins.

# Notes

Your code does not need to be deterministic. That is random sampling methods are allowed as long as they give the right answer at least 9 times out of the first 10 times I test them.

# Answer
> 10 votes
# Python 3 + SciPy, score ≈ 1.86 · 10103

\\$T(n, k)\\$ approaches the normal distribution quickly enough that we can just compute it exactly for \\$n \< 97\\$ and use the CDF of the normal distribution for \\$n \ge 97\\$. This solution runs in effectively constant time. (Technically, for \\$n \> 1.86 \cdot 10^{103}\\$ the numbers start being too large to convert to `float` and we start getting `OverflowError`. This hardly matters because the answer is `0.500` for \\$n \> 1500000\\$ or so.)

```
import sys
import numpy as np
from scipy.special import erfc

n = int(sys.argv[1])
k = n * n // 4

if n < 97:
    a = np.array([1])
    for i in range(1, n + 1):
        a = np.cumsum((np.r_[a, np.ones(i)] - np.r_[np.zeros(i), a])[:-1] / i)
    out = a[k]
else:
    mean = n * (n - 1) / 4
    variance = n * (n - 1) * (2 * n + 5) / 72
    out = erfc((mean - k - 0.5) / np.sqrt(2 * variance)) / 2

print("%.3f" % (out,))

```

Try it online!

# Answer
> 0 votes
# Rust

Port of @Anders Kaseorg's Python answer in Rust.

### `/src/main.rs`

```
use std::{cmp, env, f64, sync::mpsc, thread, time::Duration};
use statrs::{
    function::erf::erfc,
    distribution::{Normal, Univariate},
};
use ndarray::{Array, Array1, Axis, stack, concatenate, s, prelude::*};
use ndarray_stats::QuantileExt;

fn main() {
    let args: Vec<String> = env::args().collect();
    if args.len() < 2 {
        println!("Please provide a command line argument 'n'.");
        return;
    }
    let n: usize = match args[1].parse() {
        Ok(val) => val,
        Err(_) => {
            println!("Invalid argument. Please provide an integer.");
            return;
        }
    };
    let k = n * n / 4;
    let mut out = 0.0;

    if n < 97 {
        let mut a = Array1::<f64>::from_elem(1, 1.0);
        for i in 1..n + 1 {
            let ones = Array1::<f64>::from_elem(i, 1.0);
            let zeros = Array1::<f64>::from_elem(i, 0.0);
            let a_extended = concatenate(Axis(0), &[a.view(), ones.view()]).unwrap();
            let zeros_extended = concatenate(Axis(0), &[zeros.view(), a.view()]).unwrap();
            let mut a_diff = &a_extended - &zeros_extended;
            a_diff = a_diff.slice(s![..-1]).to_owned();
            a_diff = a_diff / (i as f64);
            let cumsum = |x: &Array1<f64>| {
                let mut sum = 0.0;
                x.mapv(|val| {
                    sum += val;
                    sum
                })
            };
            a = cumsum(&a_diff);
        }
        out = a[cmp::min(k, a.len() - 1)];
    } else {
        let mean = n as f64 * (n as f64 - 1.0) / 4.0;
        let variance = n as f64 * (n as f64 - 1.0) * (2.0 * n as f64 + 5.0) / 72.0;
        // println!("{:.3} {:.3}",mean,variance);
        out = erfc((mean - k as f64 - 0.5) / f64::sqrt(2.0 * variance)) / 2.0;
    }
    println!("{:.3}", out);
}

```

### `Cargo.toml`

```
[package]
name = "rust_hello"
version = "0.1.0"
edition = "2021"

# See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html

[dependencies]
# rand = "0.8.0"
# hyper = "0.13"
# tokio = { version = "0.2", features = ["full"] }
# rayon = "1.5.1"

ndarray = "0.15.4"
statrs = "0.13.0"
ndarray-stats = "0.4.0"

```

### Building and running

```
# win10 environment

$ cargo build
$ target\debug\rust_hello.exe 500
$ target\debug\rust_hello.exe 100
$ target\debug\rust_hello.exe 18

```

---
Tags: fastest-code
---