0
$\begingroup$

I am developing an algorithm that uses a lookup table to process the data, I want to know how many unique tables can be created. If I have a table of 256 values I know that 256! would tell me how many tables are possible, but the math of the algorithm moves forward or backward along this table based on the calculation so the tables are essentially circular with the first and last value sitting next to each other. Because of this every table with the values in an order that would match exactly to another table except a different start/end would not be unique and not counted.

Without generating every possible table and testing it against others how do I figure out many tables are possible?

$\endgroup$
  • $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$ – Ella Rose Feb 2 '19 at 23:06
0
$\begingroup$

The number of possible unique tables for your application is $255!$. The key term you will want to look up is circular permutation.

The number of tables you can have without wrapping around is a permutation of the elements (also called a 'linear permutation'). The number of possible tables of a permutation of the elements is $n!$, which is why you (correctly) calculated the number of possible permutations of the table as $256!$.

Because your use is circular, you would need to calculate the number of unique circular permutations, which is equal to $(n-1)!$. So for the usage in your application where you have 256 elements, the number of possible tables is $(256-1)! = 255!$.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Doh! Is it really THAT easy?! [Slaps forehead] Does that cover the cyclic for each possible order? $\endgroup$ – Karæthon Feb 2 '19 at 22:54
  • $\begingroup$ Yes, it's that easy. I'm not sure what you mean by "cyclic for each possible order", but it covers all of the possible ways to arrange 256 elements in a circle, which is basically what you're question is asking about. $\endgroup$ – Brandon Feb 2 '19 at 23:22
  • $\begingroup$ Also: Having that many possible tables does NOT imply that your scheme is secure. As discussed in the chat, it's probably not. $\endgroup$ – Brandon Feb 2 '19 at 23:24
  • $\begingroup$ No it doesn't make it secure, it just adds another layer of possibilities, making hacking that much more difficult. And yes, i meant 'all the possible ways to arrange 256 elements in a circle' with 'cyclic for each possible order" $\endgroup$ – Karæthon Feb 2 '19 at 23:34
  • $\begingroup$ @Karæthon It doesn't make cracking it any more difficult at all. In fact, it's exactly as easy as if the tables were not there. $\endgroup$ – forest Feb 3 '19 at 9:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.