most recent 30 from http://mathoverflow.net 2013-05-20T15:58:02Z http://mathoverflow.net/feeds/question/110769 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/110769/permutations-balanced-distribution Joel Smith 2012-10-26T16:44:54Z 2012-10-26T16:44:54Z

<p>I would like to implement a form of consistent hashing using a set of permutations. The rules are as follows:</p> <ul> <li>I have Y=~32 buckets and X items. Buckets may be "alive" or "dead". Items are to be distributed evenly across "alive" buckets, regardless of the subset of buckets which are alive. By distributed evenly I mean that the bucket with the most items will not have many more items than the bucket with the least items (hopefully a difference of at most 1 item).</li> <li>To do this I want to generate permutations of the buckets - one permutation per item, such that each item will fall into the first "alive" bucket in that item's permutation.</li> </ul> <p>From what I can gather, if each row is a permutation and we generate a table with X rows and Y columns - we want permutations with the following traits:</p> <ul> <li>The first column should have (roughly) the same amount of appearances for each of the Y buckets.</li> <li>Assuming a subset S of the buckets are dead, all permutations which begin with a subset T of S should have (roughly) the same amount of apearances for each of the Y buckets when observing the spots directly after (T) in each of these permutations. (T is obviously not necessarily the same subset of S for each permutation)</li> </ul> <p>The questions are: Do there exist such permutations for X which is approximately equal to Y^2 or smaller, for a gap of at most 1 item between buckets in the worst case? For a gap of 2? Etc... If there do exist such permutations - how can they be built?</p>