[seqfan] A correspondent is asking for help with an idea

[Neil Sloane]

Anyone interested in helping this person?  If so, 1, post a note here
saying I'll try, and 2, contact the sender directly. No need to include me
in the loop.

This is posted here with his permission.

request for someone - not you! - to look at a possibly new, probably
useful, thingy related to permutations - from
jan <rtm443x at googlemail.com>

Dear Mr. Sloane,
I'll keep this brief. If you're too busy, please tell me to get lost.

I'm a programmer not a mathematician. I was looking at cuckoo filters.
These rely on what's seems to be called permutation packing to save
space:

If you have any to combinations of 0 and 1 and allocate a number to
these combinations and store that number instead of the combination
directly:

(0, 0) -> 0
(0, 1) -> 1
(1, 0) -> 2
(1, 1) -> 3

This saves you nothing, however if you don't care about the order then:

(0, 0) -> 0
(0, 1) -> 1
(1, 0) -> 1   because (0,1) = (1,0)
(1, 1) -> 2

At that you only have three values, which saves you a little.  In
larger combinations, this starts to save you something useful.
Trivial stuff, I know.

Cuckoo filters do this kind of thing with a large lookup table (LUT)
which is cache-unfriendly, I thought I could perhaps eliminate the
LUT.

I think I've managed to do so (replacing their 65,536 entry array with
a total size of 128KBytes for a few LUTs of about 120 bytes and a
little extra code).
I can't prove this but I've done exhaustive testing on it and it seems to
work.

I don't know if I've found something novel (unlikely) but it
definitely looks useful. I've also been unable to find anythging on
the web that looks like this (though to be fair I've no idea what to
look for but I have looked at lehmer codes - which these aren't
related to).

I've emailed the authors of the cuckoo filter but had no reply. I'm
sure they get enough nutters, I don't blame them.

This algo is exceedingly simple. I would love to know if it's new.

Can you recommend someone with a background in combinatorics who might
take a look? I can explain it in about 5 minutes in a document. I can
probably add a spreadsheet which displays each step to help, though
it's so simple that's probably unnecessary - but happy to anyway.

It is about the shape produced in an n-dimensional cube. The shape is
highly regular and can be summarised in a tiny LUT for each dimension
of the cube - order your items to be packed (these correspond to
co-ordinates within the cube), go through with a subtraction at each
sub-cube, add up at the end and you're done.
When illustrated it's totally obvious.

So, can you suggest anyone? I'd be really grateful even to find out
it's well known. At least I can forget it then.

regards


jan