in reply to Re: Pattern enumeration.
in thread Pattern enumeration.

Sorry, but your calculation is significantly too simple. An illegal board can fail more than just one constraint. Your 2*48*6*6**61 enumerates the possible paths for a simple algorithm that is guaranteed to produce an illegal board. But a huge number of those paths are just different ways of generating the same board (if a board violates 6 different constraints, then your equation will count that board 6 different times).

So you have over estimated the number of illegal boards rather significantly. This is rather easy to see by noting that your estimated number of legal boards comes out to -360*6**61. A negative number of possibilities is clearly the wrong answer.

I've computed counts for similar sets in the past. It gets very complicated very quickly. I'll try to write up at least the first part of such a calculation but I doubt I'll be posting that very soon. :)

You could get an approximate answer by generating a large number of boards at random and calculating the average number of constraints violated by a random illegal board and then using that number to divide the number you originally calculated.

- tye        

Replies are listed 'Best First'.
Re^3: Pattern enumeration. (KISS)
by BrowserUk (Patriarch) on Jul 27, 2010 at 09:35 UTC
    You could get an approximate answer by generating a large number of boards at random

    Generating random boards and then just checking for pass/fail very quickly converges to a figure of 8.9%; giving a approximation of 5.657e+48 legal boards.

    I don't understand your "calculating the average number of constraints violated by a random illegal board" bit.

    I do realise that for any given legal board, there are 720 "symmetries", where the arrangement of tokens is the same, but the actual tokens are different. Um. Not a good description.

    Ie. The following are symmetries because the pattern of the tokens remains the same, though the values of the tokens are different: 

    1 2 3    2 3 1    3 2 1
2 3 1    3 1 2    2 1 3            
3 2 1    1 3 2    1 2 3

    [download]

    For my purpose, reflection and rotational symmetries are different.

    So, I think that once I've calculated the total number of legal arrangements, I divide by 720 to determine the number of patterns?

    Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
    "Science is about questioning the status quo. Questioning authority".
    In the absence of evidence, opinion is indistinguishable from prejudice.
[reply]
[d/l]

      So, I think that once I've calculated the total number of legal arrangements, I divide by 720 to determine the number of patterns?

      A 3x3 with 4 symbols has 95,340178,068 solutions, a number that's not even divisible by 4!. This is because some solutions don't use all the available symbols.

[reply]

        Good point!

[reply]
Re^3: Pattern enumeration. (KISS)
by roboticus (Chancellor) on Jul 27, 2010 at 10:33 UTC

    tye:

    I see what you mean by "It gets very complicated very quickly". I tried to make a new calculation for the number of legal boards, and quickly got bogged down while trying to make sure I didn't count boards multiple times.

    After working on the problem for a while, I can confidently state the following: I can't afford the amount of coffee, scratch paper, erasers and pencils required for me to figure it out!

    ...roboticus

[reply]

In Section Seekers of Perl Wisdom