How to write an algorithm for finding all permutations?

Question

Algorithms

Given:
- An array of numbers, the length of the array is not known in advance, the numbers can be repeated.
- Example [1,2,6,1,3,1,1,1]
Task:
- Generate all possible permutations of this array.
- Combinations must not be repeated (for an array, [1,2,1]this is [2,1,1],[1,2,1],[1,1,2]).
- The solution must be optimal. The variant with direct enumeration of combinations of elements will take N! even if the array has duplicate elements.
What I have already tried:
- Recursive algorithm for enumeration of combinations of array elements (N!).
- The same algorithm rewritten for tail recursion (N!).
- Shuffle algorithm, it takes a lot of time to understand a unique new combination or not.
I would like to get an algorithm that at each next step, by permuting 2 or more elements, will produce a new unique combination until the combinations run out and we get the original combination.

Answer 1

C# code

Answer 2

Iterate over all possible permutations in lexicographic order until you hit the original array.
https://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D...
rain.ifmo.ru/cat/view.php/vis/combinations/permuta...
Example C++ code: coliru.stacked-crooked.com/a/5dfc5abd30ac003c Next_permutation
implementation example: en.cppreference.com/w/cpp/algorithm/next_permutation