Перестановки заданного набора


Простой аспект перебирая определенные проблемы заключается в том, что вы можете сделать большое количество заданий, в большом количестве возможных заказов, как такой алгоритм для расчета всех этих возможных заказов представляется весьма полезным.

Я разработал такой алгоритм, хотя я довольно подозрительно он имеет существенные недостатки и я почти уверен, что есть лучший способ достижения моей цели. Я прошу и если вы видите какие-либо недостатки в своем методе и если есть альтернативный способ.

Я прокомментировал то, что я считаю полезным, но в силу характера моего алгоритма это довольно запутанная. Ниже вы найдете изображение, показывающее, как этот код работает.

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";
}

Вот диаграммы, наглядно отображающей метод:

enter image description here

Я извиняюсь, если я пропустил что-то важное или необходимое.



Комментарии