-3

I have to do a permution generation of all elements from an array, but without touching elements 2 and 23 Example: array is: 3 23 2 1 4 Output:

3 23 2 1 4

3 23 2 4 1

1 23 2 3 4

1 23 2 4 3

4 23 2 3 1

4 23 2 1 3

I do not know how to realise this task without printing the same answers multiple times

#include <iostream>
using namespace std;

void printingArr(int arr[], int size)
{
    for (int i = 0; i < size; i++)
        cout << arr[i] << " ";
    cout << endl;
}

void perm(int arr[], int n, int size)
{
    if (n == 1)
        printingArr(arr, size);
    else
        for (int j = n - 1; j >= 0; j--)
        {
            if (arr[j] != arr[n - 1] && arr[j] != 23 && arr[j] != 2 && arr[n - 1] != 23 && arr[n - 1] != 2)
                swap(arr[j], arr[n - 1]);
            perm(arr, n - 1, size);
            if (arr[j] != arr[n - 1] && arr[j] != 23 && arr[j] != 2 && arr[n - 1] != 23 && arr[n - 1] != 2)
                swap(arr[n - 1], arr[j]);
        }
}

int main()
{
    int arr[] = {3, 23, 2, 1, 4};
    int size = sizeof(arr) / sizeof(arr[0]);
    perm(arr, size, size);
    cout << endl;
    system("PAUSE");
    return 0;
}
scott
  • 1
  • 2
  • Extract modifiable elements in another array `arr2` then print `std::cout << arr2[0] << 23 << 2 << arr2[1] << arr2[2];` (space omitted). – Jarod42 Nov 30 '22 at 17:30
  • 2
    excluding 2 and 23 from your algorithm is a dirty hack, and will cause you a lot headaches. you should `1.` remove 2, 23 from the list. `2.` [list all permutations](https://stackoverflow.com/questions/17396222/how-to-generate-all-permutations-of-an-array-in-sorted-order). `3.` insert 2, 23 into the results. – Stack Danny Nov 30 '22 at 17:31

1 Answers1

2
  • Make a subarray of size - 2 elements.
  • Sort it.
  • Then use std::next_permutation on that subarray.
  • Print:
    • the subarray's first element,
    • followed by the original array's second and third elements,
    • and the rest of the subarray.

[Demo]

#include <algorithm>  // copy, next_permutation, sort
#include <fmt/ranges.h>
#include <span>
#include <vector>

void perm(int arr[], int size) {
    if (size <= 3) {
        fmt::print("{}\n", fmt::join(std::span(arr, arr + size), ", "));
        return;
    }
    std::vector<int> subarr(size - 2);
    subarr[0] = arr[0];
    std::copy(arr + 3, arr + size, std::next(std::begin(subarr)));
    std::ranges::sort(subarr);
    int arr_1{ arr[1] };
    int arr_2{ arr[2] };
    do {
        fmt::print("{}, {}, {}, {}\n",
            subarr[0],
            arr_1,
            arr_2,
            fmt::join(
                std::span(std::next(std::begin(subarr)), size - 3),
                ", "
            )
        );
    } while (std::next_permutation(std::begin(subarr), std::end(subarr)));
}

int main() {
    int arr[] = {3, 23, 2, 1, 4};
    perm(arr, std::ssize(arr));
}

// Outputs:
//
//   1, 23, 2, 3, 4
//   1, 23, 2, 4, 3
//   3, 23, 2, 1, 4
//   3, 23, 2, 4, 1
//   4, 23, 2, 1, 3
//   4, 23, 2, 3, 1
rturrado
  • 7,699
  • 6
  • 42
  • 62