magic_lobster_party

  • 0 Posts
  • 128 Comments
Joined 4 months ago
cake
Cake day: March 4th, 2024

help-circle



















  • So in your code you do the following for each permutation:

    for (int i = 0; i<n;i++) {

    You’re iterating through the entire list for each permutation, which yields an O(n x n!) time complexity. My idea was an attempt to avoid that extra factor n.

    I’m not sure how std implements permutations, but the way I want them is:

    1 2 3 4 5

    1 2 3 5 4

    1 2 4 3 5

    1 2 4 5 3

    1 2 5 3 4

    1 2 5 4 3

    1 3 2 4 5

    etc.

    Note that the last 2 numbers change every iteration, third last number change every 2 iterations, fourth last iteration change every 2 x 3 iterations. The first number in this example change every 2 x 3 x 4 iterations.

    This gives us an idea how often we need to calculate how often each hash need to be updated. We don’t need to calculate the hash for 1 2 3 between the first and second iteration for example.

    The first hash will be updated 5 times. Second hash 5 x 4 times. Third 5 x 4 x 3 times. Fourth 5 x 4 x 3 x 2 times. Fifth 5 x 4 x 3 x 2 x 1 times.

    So the time complexity should be the number of times we need to calculate the hash function, which is O(n + n (n - 1) + n (n - 1) (n - 2) + … + n!) = O(n!) times.

    EDIT: on a second afterthought, I’m not sure this is a legal simplification. It might be the case that it’s actually O(n x n!), as there are n growing number of terms. But in that case shouldn’t all permutation algorithms be O(n x n!)?

    EDIT 2: found this link https://stackoverflow.com/a/39126141

    The time complexity can be simplified as O(2.71828 x n!), which makes it O(n!), so it’s a legal simplification! (Although I thought wrong, but I arrived to the correct conclusion)

    END EDIT.

    We do the same for the second list (for each permission), which makes it O(n!^2).

    Finally we do the hamming distance, but this is done between constant length hashes, so it’s going to be constant time O(1) in this context.

    Maybe I can try my own implementation once I have access to a proper computer.