Practical applications?

[Dan Spaur]

I just ran across the videos about Superpermutations and was very interested in the concept and started to think if there were any practical applications. I was about to come up with but one idea I'm hoping maybe someone here can provide assistance on if it is feasible and or as practical as it may seam. I would love to hear about other possible practical uses, but below is my thought.

Data set storage.

Assume I have a item that is customizable. Perhaps an item in a popular video game. Now the item has 6 parts and each part can be used in any order. Storing these items and who has them has several routes;

In one traditional method we have a database table "ITEM" and it has columns Player, Item_Type,Part_1,Part_2,Part_3.... This method works mostly fine but if we have 15 million players and each player has 10 of the items we have a database with 150 Million rows. While this works fine I feel it has substantial overhead in the database.

An alternative would be to "code" the item and make an ID that described it. Such as represent each "part" as a number 0-6 and put them together as  a string. So one item is represented as "123645" and with this our table could just be Player, Item_Code. This begins to streamline things a bit but the "item code" alone for 150 million lines is close to a gig of data. But it is the method I would have chosen previously however with the idea of superpermutations I wonder if the next idea is feasible.

Start with superpermutation for N=6 and save all 872 digits of the string.

"12345612345162345126345123645132645136245136425136452136451234651234156234152634..."

then when you generate the item code you simply look for its location in the string so the example of "123645" shows up 22 digits in so we can store that item as item "22" instead of "123645". This saves us a minimum of 3 bytes per line which at least cuts the data storage in half.

Tho I do wonder when you start getting larger N values how long before your starting string is too large to deal with in itself. If I understand correctly N=16 would have over a trillion digits and would need 1.3 gigs to store, but even here the idea shows its value in some cases such as when almost every person has at least one version of "0123456789ABCDEF" and that is stored in this method as a simple 1 instead of all 16 digits.

can anyone shed more light on this concept and or provide other practical usages?

[Zach Hunter]

Typically one of the practical benefits of solving such problems is simply developing the tools to solve difficult problems. While I am not aware of any direct real applications of superpermutations, the ability to solve this problem can likely be applied to solving similar problems down the road.

[Katie Anderson]

I don't think this is really a practical application. Why not just store the lexicographic (or some other) permutation index, then generate the permutation on the fly? The number of permutations is always lower than the length of the superpermutation, so you're not using any more space (saving .3 bits for n=6, but only if you use a very packed encoding) plus you don't have to generate a superpermutation or search through it when adding a new entry.

Here's some well-documented code for indexing/generating permutations that uses the factoradic number system and Lehmer codes. I'm going to look through it a bit closer - it sounds interesting!

http://keithschwarz.com/interesting/code/?dir=factoradic-permutation

[plitser]

I'm also thinking Sudoku.

[B Metz]

As for the OP's example, I don't see any advantages to superpermutations as  that would justify using strings as item id values for the pattern "compression".  How would you encode the quantity in such an implementation.

I know RDBMS' have fallen out of fashion, but an int item id plus int counter field is not going to require a gig of storage for 150M users, at least not for a single item alone if "reasonable" max item limits are set.  It would take a 4 byte id field plus 4 byte counter field to exceed 1G of storage for a single item possessed by all 150M players concurrently.  Do you really need to have ~4 billion items with up to ~4 billion of each item though?  

If limited to say 65K unique item id's and no more than 256 of each, then you are looking at a max of 450M per item if all 150M users posess at least one of that item concurrently.  Of course that does ramp up quickly over all items, but the max storage for a single item per player would never require more than 3-4B or ~196-262KB max per player?  That is a 39TB worst case scenario but the per user size doesn't seem unreasonable before considering compression or more efficient encoding schemes.  

Not an expert.  Just found the OP's proposed scenario intriguing and wanted to offer an alternative view, but one that's largely out of tune with this forum I suppose.

--
You received this message because you are subscribed to the Google Groups "Superpermutators" group.
To unsubscribe from this group and stop receiving emails from it, send an email to superpermutato...@googlegroups.com.
To view this discussion on the web, visit https://groups.google.com/d/msgid/superpermutators/490ff942-505f-4ab6-902e-8185d82515d8n%40googlegroups.com.