1
\$\begingroup\$

A simple aspect of brute forcing certain problems is that you may have to do a large numbers of tasks in large numbers of possible orders, as such an algorithm for calculating all these possible orders seems rather useful.

I have developed such an algorithm, although I'm rather suspicious it has considerable flaws and I'm almost sure there is a better way of accomplishing my goal. I am asking both if you see any flaws in my method and if there is an alternative method.

I have commented what I believe to be useful but due to the nature of my algorithm it is quite confusing. Further down you will find an image showing how this code essentially works.

const int   n = 4;//the set size

std::vector<std::vector<int>> getOrders(const std::vector<int> & set);
std::vector<int> shiftAroundIndex(const std::vector<int> & set, int index, int numbOfShifts);
std::vector<int> shiftArray(const std::vector<int> & set, int numbOfShifts);
void printSet(const std::vector<int> & set);
void printSet(const std::vector<std::vector<int>> & set);

int main() {
    std::vector<int> orderArray;
    for (int i = 0; i < n; i++) {
        orderArray.push_back(i);
    }
    std::vector<std::vector<int>> orders = getOrders(orderArray);
    printSet(orders);
    std::cout << "Combinations: " << orders.size() << std::endl;
    system("pause");
    return 0;
}

std::vector<std::vector<int>> getOrders(const std::vector<int> & set) {
    std::vector<std::vector<int>> returnArray;//vector to contain all orderings
    std::vector<int> checkingHolder;//vector to hold current ordering being calculated
    for (int i = 0; i < n; i++) {
        returnArray.push_back(shiftArray(set, i));
        //getting all basic rotations E.g. for {1,2,3} this would be {3,1,2}, {2,3,1} and {1,2,3}
    }
    bool repeatedSet;
    for (int i = 0; i < n; i++) {//basic rotation to adapt
        for (int t = 0; t < n; t++) {//index to rotate around
            repeatedSet = false;
            for (int u = 1; true; u++) {//how many times to rotate around index
                checkingHolder = shiftAroundIndex(returnArray[i], t, u);
                for (int q = 0; q < returnArray.size(); q++) {
                    if (returnArray[q] == checkingHolder) {//if new order has already been calculated
                        repeatedSet = true;
                        break;
                    }
                }
                if (repeatedSet) {
                    /* if new order has already been calculated then 
                     * further rotations will produce more orders that have also been already calculated
                    */
                    break;
                }
                returnArray.push_back(checkingHolder);
                //push newly calculated order to vector of all previously calculated orderings
            }
        }
    }
    return returnArray;
}

std::vector<int> shiftAroundIndex(const std::vector<int> & set, int index, int numbOfShifts) {
    std::vector<int> holder (set);
    if (numbOfShifts > 0) {
        for (int i = 0; i < holder.size(); i++) {
            if (i == index) {
                continue;
            }
            if (i + 1 == index) {
                if (index == holder.size() - 1) {
                    holder[0] = set[i];
                }
                else {
                    holder[i + 2] = set[i];
                }
            }
            else if (i == holder.size() - 1) {
                if (index == 0) {
                    holder[1] = set[i];
                }
                else {
                    holder[0] = set[i];
                }
            }
            else {
                holder[i + 1] = set[i];
            }
        }
        if (numbOfShifts > 1) {
            return shiftAroundIndex(holder, index, numbOfShifts - 1);
        }
    }
    return holder;
}

std::vector<int> shiftArray(const std::vector<int> & set, int numbOfShifts) {
    std::vector<int> holder (set);

    if (numbOfShifts > 0) {
        for (int i = 1; i < holder.size() + 1; i++) {
            if (i == holder.size()) {
                holder[0] = set[i - 1];
            }
            else {
                holder[i] = set[i - 1];
            }
        }
        if (numbOfShifts > 1) {
            return shiftArray(holder, numbOfShifts - 1);
        }
    }
    return holder;
}

void printSet(const std::vector<int> & set) {
    std::cout << "\n{" << set[0];
    for (int i = 1; i < set.size(); i++)
    {
        std::cout << "," << set[i];
    }
    std::cout << "}";
}

void printSet(const std::vector<std::vector<int>> & set) {
    std::cout << "\n{";
    for (int i = 0; i < set.size(); i++)
    {
        printSet(set[i]);
    }
    std::cout << "\n}\n";
}

Here is the diagram displaying the method:

enter image description here

I apologise if I have missed anything important or necessary.

\$\endgroup\$
  • \$\begingroup\$ Why not use std::next_permutation? \$\endgroup\$ – Edward Mar 13 '18 at 16:56
  • \$\begingroup\$ @Edward I beleive the permutations of a given set can be proper subsets of said set, for example {2,1} is a permutation of {1,2,3}. This is not my goal here. This is at least how permutations are defined from a mathematical perspective. \$\endgroup\$ – Jonathan Woollett-light Mar 13 '18 at 17:21
  • 1
    \$\begingroup\$ @Edward Having now read the description of that function, I was frankly unaware of it since it would seem the meaning of a permutation is different in this circumstance. Although I would still like to know the actual method behind that function. \$\endgroup\$ – Jonathan Woollett-light Mar 13 '18 at 17:29
  • 1
    \$\begingroup\$ "Although I would still like to know the actual method behind that function." What's stopping you from looking at it? \$\endgroup\$ – yuri Mar 13 '18 at 17:45
  • 1
    \$\begingroup\$ There is an example implementation on the link I referenced in my comment. \$\endgroup\$ – Edward Mar 13 '18 at 18:07

Your Answer

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

Browse other questions tagged or ask your own question.