dcsimg
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Page 3 of 3 FirstFirst 123
Results 31 to 33 of 33

Thread: Set of Unique pairs

  1. #31
    Join Date
    Feb 2017
    Posts
    506

    Re: Set of Unique pairs

    Quote Originally Posted by 2kaud View Post
    There are more than 2 sets of solutions for 6 numbers
    Yes I've realized that so I removed my failed solution.
    Last edited by wolle; January 10th, 2020 at 03:50 PM.

  2. #32
    Join Date
    Feb 2017
    Posts
    506

    Re: Set of Unique pairs

    Quote Originally Posted by wolle View Post
    Yes I've realized that so I removed my failed solution.
    Well, it turns out I was on the right track after all so I restore the solution and continue.

    I had the idea that a pair (i,j) can be viewed as a square on a 6 by 6 chess board. We place 6 rocks on the board so that no rock threats any other rock. It is called a valid 6-rock configuration. We make sure that no rock is placed in the diagonal going from upper left to lower right. This is because the pair (i,j) to describe this position will have i=j and such a pair can never be part of a valid set (because if the members of one pair are equal then the set cannot go from 1 to 6).

    A 6-rock configuration will represent 6 pairs and it turns out that they can always be used to form 2 sets of 3 pairs where both set abide by the 1 to 6 rule. This is extraordinary and at this point I don't know exactly why it works (well it seems it doesn't always work. I'll have to check it out. Or maybe I leave it as an exercise for the OP ).

    The solution strategy is to fill the whole chess board with as many valid 6-rock configurations as possible. To do it systematically we start with the diagonal going from lower left to upper right. We then take the diagonal below, and then the one below again etcetera until the whole board is filled with rocks. I name the configurations 1 to 5 and this is how the board turns out:

    x 3 5 2 4 1
    3 x 4 5 1 2
    5 4 x 1 2 3
    2 5 1 x 3 4
    4 1 2 3 x 5
    1 2 3 4 5 x

    Note that no rock in any configuration threats another rock within the same configuration.

    If we turn the rock configurations into pair equivalents we have

    Conf. 1 : (6,1), (5,2), (4,3), (3,4), (2,5), (1,6)
    Conf. 2 : (6,2), (5,3), (3,5), (2,6), (4,1), (1,4)
    Conf. 3 : (6,3), (5,4), (4,5), (3,6), (2,1), (1,2)
    Conf. 4 : (6,4), (4,6), (5,1), (3,2), (2,3), (1,5)
    Conf. 5 : (6,5), (5,6), (4,2), (3,1), (2,4), (1,3)

    We re-organize these configurations into 2 sets of 3 pairs making sure both sets abide by the 1 to 6 rule

    Conf. 1 : {(6,1), (5,2), (4,3)}, {(3,4), (2,5), (1,6)}
    Conf. 2 : {(6,2), (5,3), (4,1)}, {(2,6), (3,5), (1,4)}
    Conf. 3 : {(6,3), (5,4), (2,1)}, {(3,6), (4,5), (1,2)}
    Conf. 4 : {(6,4), (3,2), (5,1)}, {(4,6), (2,3), (1,5)}
    Conf. 5 : {(6,5), (3,1), (4,2)}, {(5,6), (2,4), (1,3)}

    This, ladies and gentlemen, is an optimal solution. All possible pairs are present exactly once. It means there are no repeated pairs and there are no pairs left to form more sets. There are 10 sets in total, all abiding with the 1 to 6 rule.
    Last edited by wolle; January 12th, 2020 at 05:06 AM.

  3. #33
    2kaud's Avatar
    2kaud is offline Super Moderator Power Poster
    Join Date
    Dec 2012
    Location
    England
    Posts
    6,972

    Re: Set of Unique pairs

    All advice is offered in good faith only. All my code is tested (unless stated explicitly otherwise) with the latest version of Microsoft Visual Studio (using the supported features of the latest standard) and is offered as examples only - not as production quality. I cannot offer advice regarding any other c/c++ compiler/IDE or incompatibilities with VS. You are ultimately responsible for the effects of your programs and the integrity of the machines they run on. Anything I post, code snippets, advice, etc is licensed as Public Domain https://creativecommons.org/publicdomain/zero/1.0/ and can be used without reference or acknowledgement. Also note that I only provide advice and guidance via the forums - and not via private messages!

    C++17 Compiler: Microsoft VS2019 (16.4.2)

Page 3 of 3 FirstFirst 123

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  


Windows Mobile Development Center


Click Here to Expand Forum to Full Width




On-Demand Webinars (sponsored)