# [C#] Convert "1,2,3,4,5....,N" to "632,124,364,983, ...., etc".

## Recommended Posts

Thevenin    270
I have a need to turn a sequence into apparent randomness, and then be able to turn it back again. For instance, I pass it "1" it returns "636", I pass it "2" it returns "125". And it's completely reversible. I say reverse("636") and I get "1". The range of values for input is in the billions, so simply storing a lookup table isn't going to help. Know of any .NET libraries that are designed for this? So I don't have to go invent my own contraption. =/

##### Share on other sites
Sneftel    1788
It all depends on how apparent you want the randomness to be. XOR is easy, fast, and trivially reversible.

##### Share on other sites
Thevenin    270
Quote:
 Original post by SneftelIt all depends on how apparent you want the randomness to be. XOR is easy, fast, and trivially reversible.

A simple XOR will not give the level of randomness I need. If I'm thinking straight, XOR would give me about B sequential series of consecutive numbers (I don't know if that makes logical sense) where B is the number of bits in the XOR code,

"1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,...."

Transforms into:

"100, 500, 400, 101, 501, 401, 102, 502, 402, 103,503,403"

Least, I think this is how it would look...

Edit:/ I cannot believe I'm googling for "reversible randomize function", lol..

##### Share on other sites
NickHighIQ    100
You could still use XOR, but add a key-value (like n, the number of input values) to each number in the sequence before and/or after XOR-ing it.

##### Share on other sites
Sneftel    1788
If you don't want consecutive runs, just shuffle the bits afterwards.

##### Share on other sites
SiCrane    11839
You might have better luck searching for "involution"/"involutary function", mathematical terms for a function is its own inverse or "reciprocal cipher" which is the cryptographic term for a encryption method that is its own inverse.

##### Share on other sites
MaR_dev    154

http://objectmix.com/c/242647-reversible-random-generator.html

Solution sounds simple and like something you could use.

##### Share on other sites
HappyCoder    5052
I would just have a set pattern you use to switch up bits, then do an XOR to invert some of them.
value 0 0 0 1 0 1 0 1bit   0 1 2 3 4 5 6 7

goes to
value 1 0 0 0 1 0 0 1bit   3 6 2 0 7 1 4 5

10001001 ^ 00101101 -> 10100100

to undo it just do it backward.
XOR with the same mask.encoded    mask10100100 ^ 00101101 -> 10001001

Then reverse the scramble.

That should yield pretty random looking results.

EDIT:
or for even more random like results you could also set the seed of a random number. Use that random seed to generate a random number to do the mask with or even to switch bits with. Then when you save the number save the seed you used in front of the number.

##### Share on other sites
Thevenin    270
I'm still googling around, I'll try 'involution' in my search terms.

Bitwise operations in C# arn't fun.. I made a bug in my code just now, but I don't know if I really want to pursue using my own invention for this:

using System;using System.Collections.Generic;using System.Text;class cBitShuffle{    private const int MyCode = (unchecked((int)0xB00B1EE5));    private static void sSwapBit(ref int TheNumber, int TheLocation1, int TheLocation2)    {        if (!(TheLocation1 >= 0 && TheLocation1 < 32) ||            !(TheLocation2 >= 0 && TheLocation2 < 32))            throw new Exception("Location index must be in range [0..31].");        if (TheLocation1 == TheLocation2) return;        /* Get the bits. */        int TheBit1 = (TheNumber & (1 << TheLocation1)) > 0 ? 1 : 0;         int TheBit2 = (TheNumber & (1 << TheLocation2)) > 0 ? 1 : 0;        /* Clear bits. */        TheNumber &= (int)(0xFFFFFFFF ^ (1 << TheLocation1));        TheNumber &= (int)(0xFFFFFFFF ^ (1 << TheLocation2));        /* Set the bits. */        TheNumber |= TheBit1 << TheLocation2;        TheNumber |= TheBit2 << TheLocation1;    }    static int sEncode(int TheNumber)    {        /* First, NOR it with boobiees. */        TheNumber ^= MyCode;        /* Then swap like a flipflop. */        for (int TheLoop = 0; TheLoop < 32; TheLoop++)            sSwapBit(ref TheNumber, TheLoop, (TheLoop * 3) % 32);        return TheNumber;    }    static int sDecode(int TheNumber)    {        /* First, undo the swaps. */        for (int TheLoop = 0; TheLoop < 32; TheLoop++)            sSwapBit(ref TheNumber, TheLoop, (TheLoop * 3) % 32);        /* Then, undo the NOR it with boobiees. */        TheNumber ^= MyCode;        return TheNumber;    }    static void Main(string[] args)    {        for (int TheLoop = 0; TheLoop < 100; TheLoop++)            Console.WriteLine(TheLoop.ToString() + "\t" + sEncode(TheLoop) + "\t" + sDecode(sEncode(TheLoop)));        Console.ReadKey();    }}

##### Share on other sites
HappyCoder    5052
Quote:
 Original post by TheveninI'm still googling around, I'll try 'involution' in my search terms.Bitwise operations in C# arn't fun.. I made a bug in my code just now, but I don't know if I really want to pursue using my own invention for this:*** Source Snippet Removed ***

I think you want to loop backwards through the decode loop

    static int sDecode(int TheNumber)    {        /* First, undo the swaps.*/        for (int TheLoop = 31; TheLoop >= 0; TheLoop--)            sSwapBit(ref TheNumber, TheLoop, (TheLoop * 3) % 32);        /* Then, undo the NOR it with boobiees. */        TheNumber ^= MyCode;        return TheNumber;    }

##### Share on other sites
Thevenin    270
Quote:
 Original post by HappyCoderI think you want to loop backwards through the decode loop

I think you're right! [smile]

I also noticed another mistake, and an optimization (check if TheBit1 == TheBit2) I should have put in.

Mistake (because result can be negative).
int TheBit1 = (TheNumber & (1 << TheLocation1)) > 0 ? 1 : 0;
int TheBit2 = (TheNumber & (1 << TheLocation2)) > 0 ? 1 : 0;
Correct
int TheBit1 = (TheNumber & (1 << TheLocation1)) == 0 ? 0 : 1;
int TheBit2 = (TheNumber & (1 << TheLocation2)) == 0 ? 0 : 1;

Output (not impressive):
0       1021392911      01       1021392910      12       1021523983      23       1021523982      34       1021392907      45       1021392906      56       1021523979      67       1021523978      78       1054947343      89       1054947342      910      1055078415      1011      1055078414      1112      1054947339      1213      1054947338      1314      1055078411      1415      1055078410      1516      1021392927      1617      1021392926      1718      1021523999      1819      1021523998      1920      1021392923      2021      1021392922      2122      1021523995      2223      1021523994      2324      1054947359      2425      1054947358      2526      1055078431      2627      1055078430      2728      1054947355      2829      1054947354      2930      1055078427      3031      1055078426      3132      1021384719      3233      1021384718      3334      1021515791      3435      1021515790      3536      1021384715      3637      1021384714      3738      1021515787      3839      1021515786      3940      1054939151      4041      1054939150      4142      1055070223      4243      1055070222      4344      1054939147      4445      1054939146      4546      1055070219      4647      1055070218      4748      1021384735      4849      1021384734      4950      1021515807      5051      1021515806      5152      1021384731      5253      1021384730      5354      1021515803      5455      1021515802      5556      1054939167      5657      1054939166      5758      1055070239      5859      1055070238      5960      1054939163      6061      1054939162      6162      1055070235      6263      1055070234      6364      1017198607      6465      1017198606      6566      1017329679      6667      1017329678      6768      1017198603      6869      1017198602      6970      1017329675      7071      1017329674      7172      1050753039      7273      1050753038      7374      1050884111      7475      1050884110      7576      1050753035      7677      1050753034      7778      1050884107      7879      1050884106      7980      1017198623      8081      1017198622      8182      1017329695      8283      1017329694      8384      1017198619      8485      1017198618      8586      1017329691      8687      1017329690      8788      1050753055      8889      1050753054      8990      1050884127      9091      1050884126      9192      1050753051      9293      1050753050      9394      1050884123      9495      1050884122      9596      1017190415      9697      1017190414      9798      1017321487      9899      1017321486      99

##### Share on other sites
Thevenin    270
Quote:
 Original post by HappyCoderI would just have a set pattern you use to switch up bits, then do an XOR to invert some of them.

Tried that. I removed the loop and just swapped some of the bits I thought would have the most probably chance of returning drastically different numbers. The output I get is:

0       B00B96E5        01       300B96E5        12       B00B96E7        23       300B96E7        34       A00B96E5        45       200B96E5        56       A00B96E7        67       200B96E7        78       B00B96ED        89       300B96ED        910      B00B96EF        1011      300B96EF        1112      A00B96ED        1213      200B96ED        1314      A00B96EF        1415      200B96EF        1516      B00B96F5        1617      300B96F5        1718      B00B96F7        1819      300B96F7        1920      A00B96F5        2021      200B96F5        2122      A00B96F7        2223      200B96F7        2324      B00B96FD        2425      300B96FD        2526      B00B96FF        2627      300B96FF        2728      A00B96FD        2829      200B96FD        2930      A00B96FF        3031      200B96FF        3132      B00B96C5        3233      300B96C5        3334      B00B96C7        3435      300B96C7        3536      A00B96C5        3637      200B96C5        3738      A00B96C7        3839      200B96C7        3940      B00B96CD        4041      300B96CD        4142      B00B96CF        4243      300B96CF        4344      A00B96CD        4445      200B96CD        4546      A00B96CF        4647      200B96CF        4748      B00B96D5        4849      300B96D5        4950      B00B96D7        5051      300B96D7        5152      A00B96D5        5253      200B96D5        5354      A00B96D7        5455      200B96D7        5556      B00B96DD        5657      300B96DD        5758      B00B96DF        5859      300B96DF        5960      A00B96DD        6061      200B96DD        6162      A00B96DF        6263      200B96DF        6364      B00B96A5        6465      300B96A5        6566      B00B96A7        6667      300B96A7        6768      A00B96A5        6869      200B96A5        6970      A00B96A7        7071      200B96A7        7172      B00B96AD        7273      300B96AD        7374      B00B96AF        7475      300B96AF        7576      A00B96AD        7677      200B96AD        7778      A00B96AF        7879      200B96AF        7980      B00B96B5        8081      300B96B5        8182      B00B96B7        8283      300B96B7        8384      A00B96B5        8485      200B96B5        8586      A00B96B7        8687      200B96B7        8788      B00B96BD        8889      300B96BD        8990      B00B96BF        9091      300B96BF        9192      A00B96BD        9293      200B96BD        9394      A00B96BF        9495      200B96BF        9596      B00B9685        9697      300B9685        9798      B00B9687        9899      300B9687        99

##### Share on other sites
Deaken Frost    133
Seriously, just use a block cipher. Take your numbers and encrypt them. Presto, seemingly random numbers. To get them back just decrypt. It's really that simple.

.NET already has everything you need.

##### Share on other sites
Thevenin    270
Quote:
 Original post by Deaken Frost...just use a block cipher. [...]

Block cipher looks like it could do it. However, a few things I hadn't throughly thought of arose and made me realize I should really tackle this at the source (in the database, in the stored procedure that originated this mess), I'm actually surprised that no one asked me "Why do you need to convert this sequence?" since that's usually the first question. My T-SQL is a bit hackish but, a solution nevertheless.

		-- Find us a random character id that isn't already taken.		WHILE @TheShouldLoop = 1			BEGIN				SET @TheGenCharID = rand() * 2147483647;				SET @TheError = @@ERROR;				IF @TheError != 0 GOTO lblHandleError;								SET @TheCharacterCount = (SELECT COUNT(*) FROM fw_character WHERE					char_characterid = @TheGenCharID);				SET @TheError = @@ERROR;				IF @TheError != 0 GOTO lblHandleError;							IF(@TheCharacterCount = 0)					SET @TheShouldLoop = 0;			END

Speaking of SQL, I wonder if Superpig would mind converting my 100+ line SQL statements (that employ cursors, loops, etc) into 5 line "wonders" again.

##### Share on other sites
krez    443
What version of SQL Server are you using? Doing that at the T-SQL level is not efficient (or even close to it)... if you are using 2005 you can use the crypto functions built in, or write a CLR procedure. Even in 2000 you could write a user defined function, compile it to a DLL, and call that.

I don't know why you are doing this but it isn't something that should be done in the database, at least not like that.

##### Share on other sites
Julian90    736
A simple sequence which should yield reasonable results is (x + x0)^2 + c mod p where x0 and c are arbitrary parameters and p is a prime over twice the size of the largest number you need to "randomize" (this becomes important later).

Now to decode this we have

   e = (x + x0)^2 + c mod p=> (x + x0)^2 = e - c mod p

And so we can find x + x0 by applying the Shanks-Tonelli algorithm which will yield two roots, from these we can calculate two values for x and we can select the correct value based on the fact that all of our x are in the range [0, p / 2].

##### Share on other sites
Thevenin    270
Quote:
 Original post by krezDoing that at the T-SQL level is not efficient (or even close to it)...

The code is a bit juvenile, but it'd never be a bottleneck. This code is only executed when a new account is created, and given that collisions are very rare (even when the database gets large; the server would roll-over and die long before collisions became too common for this method to work) and that the query that checks for collisions is just a simple select on a primary key, it's going to complete very very very fast.

Quote:
 Original post by krezI don't know why you are doing this but ...

In most MMORPGs your (ASCII) name is a unique identifier (at least for each realm). In Frostwinds your (UTF-8) name is not unique. Thus it's possible for you and all your friends to be named "龙火".

In addition to a well featured "buddy list" component, 8 digit hex numbers are displayed in small print on the forums, and via a right click option in-game.

Pictar (from Frostwinds forum)

It would be very lame if this hex code started at 00000000 and worked its way up. So it needs to be random. At the moment the code to generate it is quite horrific, and this T-SQL code I wrote should be quite an improvement.

##### Share on other sites
Zahlman    1682
class randomIdCollection {  std::vector <int> forward;  std::map<int, int> reverse;  public:  int translate_forward(int index) {    if (index > forward.size()) { throw std::out_of_bounds(); } // or something    return forward[index];  }  int translate_backward(int value) {    std::map<int, int>::iterator it = reverse.find(value);    if (it == reverse.end()) { throw std::out_of_bounds(); } // or something    return it->second;  }  void generate() {    int value;    do { value = getRandomValue(); }    while (std::find(forward.begin(), forward.end(), value) != forward.end());    reverse[value] = forward.size();    forward.push_back(value);  }};

##### Share on other sites
Wan    1366
Why not use MSSQL's* GUID generator NEWID(), store it in the user's record (using the function as the default value is even easier) and be done with it? Why does it have to be reversible?

* I believe that's the engine you're using, right?

##### Share on other sites
thedustbustr    191
Quote:
 It would be very lame if this hex code started at 00000000 and worked its way up.

its very lame to take what should be a trivial implementation detail, and make it complicated to the point of needing help to get it right.

KISS

##### Share on other sites
Thevenin    270
Quote:
Original post by thedustbustr
Quote:
 It would be very lame if this hex code started at 00000000 and worked its way up.

its very lame to take what should be a trivial implementation detail, and make it complicated to the point of needing help to get it right.

You mean that it's lame to ask a very concise cryptological question and then diverge the discussion into what I'm trying to accomplish (on a higher level) and how best to do it.

Although I agree with you, and I'd like GameDev to take a more ExpertsExchange approach ("[solved]" "[unsolved]" tags). The adminstrators here don't. I'm pretty sure topic divergence is still a common occurance around here; though I haven't been active here in a couple years.

And at the very least, bare with me here, the divergence occurred because the most straight-forward advice I was being given was also wrong advice; XOR and bit-shifting doesn't work (I think I even (correctly)predicted the pattern that would result in the second post).

Quote:
 Original post by thedustbustrWhy not use MSSQL's* GUID generator NEWID(), store it in the user's record (using the function as the default value is even easier) and be done with it? Why does it have to be reversible?

Can I specify the length of a GUID? Although the user isn't going to be typing these 8 digit hex keys on a regular basis (if ever), they need to be able to differentiate between which key is their friend, and which key is the name-fake user. I expect my players to be able to memorize the keys of people they trust in the game, or at the least, be able (to a high-degree of accuracy) to spot a wrong key.

And a bigger problem, GUIDs are not unique (despite its name). MSSQL may do some automated stuff to assist me in having GUIDs as primary keys (presuming I can do that) but I'd still be using a loop in the stored procedure. The difference is that the frequency of collisions would be sooo small that I'd almost be comfortable telling someone "trust me, it'll never happen".

And the only time it has to be reversible is when it's mapping "1,2,3" to "632","142","535". Perhaps I'd best explain it with the following diagrams:

System 1 (original topic):

To get random and unique 8 digit hex keys (ex "3F426285" "6F4662A") for the user, build a PRIMARY KEY as an INT and set it to AUTO_INCREMENT (by 1) starting at 0. Then, before the value of the PRIMARY KEY is displayed to the user (because it'll be "0,1,2,3,4"), map it to my reversible-randomize function ("646","252","845"). In which, a reverse function is needed to convert user input (aka "Delete character [252]") to the subsequent SQL query ("DELETE FROM tb_characters WHERE char_id=1;");.

System 2 (diverged topic):

To get random and unique 8 digit hex keys (ex "3F426285" "6F4662A") for the user, build a PRIMARY KEY as an INT, and probe it with random numbers( via rand()) until one is found that isn't already taken. This key can be displayed to the user without the need of passing it through a mapping function, and it subsequently doesn't have to be reversed.

Quote:
 Original post by Zahlman std::vector forward; std::map reverse; do { value = getRandomValue(); } while (std::find(forward.begin(), forward.end(), value) != forward.end()); reverse[value] = forward.size(); forward.push_back(value);

You've given it STATE! [bawling]

If I'm reading this right (because C++ is an eye-sore), you're making a resizable lookup table. Whenever a new account is registered, you assign the value of the account number X (example "1") to this class which maps it to a random (and unique) value Y (example "6326363"). I don't like your use of std::find, since it appears that this is going to be both linear and a memory-hog when the list grows large, nor do I much like that this converter now has state that I need to carefully preserve (which I'd best do by rewriting this code in the T-SQL language using a table that maps PK x and UK y (y of which, would be computed by probing the table with rand() to find an empty slot, much like how my current T-SQL solution does), and since calls to this generate() would be ASYNC (two people try to create an account at the same time) and thus, need to be SYNC'd via BEGIN TRANSACTION)) but it would work.

I think this thread is solved, lol...

##### Share on other sites
Wan    1366
Quote:
Original post by Thevenin
Quote:
 Original post by WanMasterWhy not use MSSQL's* GUID generator NEWID(), store it in the user's record (using the function as the default value is even easier) and be done with it? Why does it have to be reversible?

Can I specify the length of a GUID?

No you can't. You can cast it to a string and truncate it, but that would seriously damage it uniqueness.

Quote:
 Although the user isn't going to be typing these 8 digit hex keys on a regular basis (if ever), they need to be able to differentiate between which key is their friend, and which key is the name-fake user. I expect my players to be able to memorize the keys of people they trust in the game, or at the least, be able (to a high-degree of accuracy) to spot a wrong key.

Not to criticize your design, but is forcing people to memorize or recognize a random sequence of characters really the best solution?

Quote:

Correct.

Quote:
 And a bigger problem, GUIDs are not unique (despite its name). MSSQL may do some automated stuff to assist me in having GUIDs as primary keys (presuming I can do that) but I'd still be using a loop in the stored procedure.

Quote:
 And the only time it has to be reversible is when it's mapping "1,2,3" to "632","142","535".

I still don't understand the need of them, nor why they have to be reversible. However, if the about uniqueness and the ability to map them to (auto incrementing) integers, why not generate a table for them, consisting only of a primary integer key and a field for the unique code, and generate a couple of million (or whatever you'll need in the next ten years) records with any random function you like? A table lookup will probably outperform any random or hash function you write: its key is unique, it will have a clustered index and the code is a fix length char array. A database select query doesn't get any faster than that.

I'd say keep it simple and make use of the incredible optimizations in the database engine itself. And if you are concerned with state: the entire database is nothing but state.

Quote:
 I think this thread is solved, lol...

Couldn't resist to reply anyway. [smile]

##### Share on other sites
Thevenin    270
Quote:
 Original post by WanMasterNot to criticize your design, but is forcing people to memorize or recognize a random sequence of characters really the best solution?

Given that Unicode name support is a must, it was the only solution. Thus it's inherently the worst solution, and the best solution. Dunno if it's a good solution though.

This is a bit confusing.
But unicode character list is awesome!
I miss playing with my pixelated Friends from Europe/Brazil/China/Japan. =(

Quote:
Quote:
 I think this thread is solved, lol...

Couldn't resist to reply anyway. [smile]

...

So how was your day? lol [grin]

A friend of mine (who's also a lab partner of mine) intends on dropping this semester's communication systems course (3rd year computer engineering). I'm so sad -- curse this University and its extortion on students. [bawling]

[Edited by - Thevenin on March 3, 2008 5:13:00 PM]

##### Share on other sites
Zahlman    1682
Quote:
 Original post by TheveninYou've given it STATE! [bawling](But your code would work)

[lol]

Quote:
 If I'm reading this right (because C++ is an eye-sore), you're making a resizable lookup table. Whenever a new account is registered, you assign the value of the account number X (example "1") to this class which maps it to a random (and unique) value Y (example "6326363"). I don't like your use of std::find, since it appears that this is going to be both linear and a memory-hog when the list grows large,

It ought to just look up in the map instead, which would be O(lg N). I don't know why I changed that from what I had originally. :S