NB. In c I'd use an algorithm such as
BS =: 8 NB. block size
BLOCK =: 2^BS
NB. convert to blocks with padding
BLOCKED_DATA =: BS (#.\~ -)~ BINARY_DATA
count_bits =: +/"1@:#:
assert 0 1 5-:count_bits 2b0 2b1000 2b110010010100
NB. crucial idea, use known time for bit counting
COUNTS =: ([: count_bits i.) BLOCK
HIGHS =: BLOCKED_DATA ([: +/ {) COUNTS
NB. Maybe we're just looking for
HIGHS =: +/BINARY_DATA
LOWS =: (HIGHS -~ #) BINARY_DATA
SORTED_BINARY_DATA =: (LOWS , HIGHS) # 0 1
On 03/06/2014 07:00 AM, [email protected] wrote:
Date: Wed, 5 Mar 2014 20:52:35 -0800
From: Roger Hui<[email protected]>
To: Programming forum<[email protected]>
Subject: Re: [Jprogramming] a good bar bet!
Message-ID:
<camz_i_byhhgpqkvmbufbfx3g9292sc2xvhzkqjcovhhwbdi...@mail.gmail.com>
Content-Type: text/plain; charset=UTF-8
How about an extreme version of the sort problem. Suppose x is a vector of
bits (such as they have in APL). How do you sort x?
This would have been one way to solve the sorting small integers problem:
figure out how to sort 0-1 vectors and then work your way up from that. I
once posed the 88 Hats
Problem<http://www.jsoftware.com/jwiki/Essays/88_Hats>to a very smart
and very persistent intern. He solved it by generalizing a
solution to the 2 Hats problem.
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
