[wplug] OT - programming logic help

[terry mcintyre]

If you don't want a recursive solution, try this http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_cs;action=display;num=1196408518;start=6#6


 Terry McIntyre <terrymcintyre at yahoo.com>


"Government is an association of men who do violence to the rest of us."
- Leo Tolstoy




________________________________
From: Ryan W. Frenz <rfrenz at gmail.com>
To: General user list <wplug at wplug.org>
Sent: Thursday, April 23, 2009 8:39:58 AM
Subject: Re: [wplug] OT - programming logic help

> On Thu, Apr 23, 2009 at 10:58 AM, Chris Romano <romano.chris at gmail.com> wrote:
>> Here are all the possible combos ... (it's easy to do on paper, just
>> can't figure how to do this with code).

Hi Chris,

The below is in C++, but like you said, the logic should transfer to
any language.  The key is the recursion.

Ryan

#include <iostream>
#include <vector>
#include <algorithm>

typedef std::vector<int> NumberList;
typedef std::vector<NumberList> ListPermutation;

ListPermutation getPermutations(NumberList numbers) {
    ListPermutation returns;

    // Prune the recursion, just return both permutations of the pair.
    if (numbers.size() == 2) {
        returns.push_back(numbers);
        std::swap(numbers[0], numbers[1]);
        returns.push_back(numbers);
        return returns;
    }

    int index = 0;
    for (NumberList::const_iterator nIt = numbers.begin(); nIt !=
numbers.end(); ++nIt, ++index) {
        // Remove the current number and compute permutations of the others.
        NumberList otherNumbers(numbers);
        otherNumbers.erase(otherNumbers.begin() + index);

        // Add the 'fixed' number to the sub-permutations.
        const ListPermutation subPerm = getPermutations(otherNumbers);
        for (ListPermutation::const_iterator lpIt = subPerm.begin(); lpIt !=
subPerm.end(); ++lpIt) {
            NumberList fullPerm;    fullPerm.push_back(*nIt);
            fullPerm.insert(fullPerm.end(), (*lpIt).begin(), (*lpIt).end());
            returns.push_back(fullPerm);
        }
    }

    return returns;
}

int main(int argc, char* argv[]) {
    NumberList vals;
    vals.push_back(1);
    vals.push_back(2);
    vals.push_back(3);
    vals.push_back(4);
    vals.push_back(5);

    const ListPermutation perms = getPermutations(vals);
    for (ListPermutation::const_iterator pIt = perms.begin(); pIt !=
perms.end(); ++pIt) {
        for (NumberList::const_iterator ppIt = (*pIt).begin(); ppIt !=
(*pIt).end(); ++ppIt)
            std::cerr << *ppIt << " ";
        std::cerr << "\n";
    }
}


-- 
Ryan W. Frenz
rfrenz at gmail.com
_______________________________________________
wplug mailing list
wplug at wplug.org
http://www.wplug.org/mailman/listinfo/wplug



      
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.wplug.org/pipermail/wplug/attachments/20090423/81ef39ee/attachment.html