<jupyter_start><jupyter_text>This notebook was prepared by [<NAME>](https://github.com/donnemartin). Source and license info is on [GitHub](https://github.com/donnemartin/interactive-coding-challenges).  Challenge Notebook  Problem: Find all permutations of an input string.* [Constraints](Constraints)* [Test Cases](Test-Cases)* [Algorithm](Algorithm)* [Code](Code)* [Unit Test](Unit-Test)* [Solution Notebook](Solution-Notebook)  Constraints* Can the input have duplicates?    * Yes* Can the output have duplicates?    * No* Is the output a list of strings?    * Yes* Do we have to output the results in sorted order?    * No* Can we assume the inputs are valid?    * No* Can we assume this fits memory?    * Yes  Test Cases* None -> None* '' -> ''* 'AABC' -> ['AABC', 'AACB', 'ABAC', 'ABCA',             'ACAB', 'ACBA', 'BAAC', 'BACA',             'BCAA', 'CAAB', 'CABA', 'CBAA']  AlgorithmRefer to the [Solution Notebook]().  If you are stuck and need a hint, the solution notebook's algorithm discussion might be a good place to start.  Code<jupyter_code>import itertools
import sys
class Permutations(object):
    # start from the smallest lexicographical permutation. For "CBA" that is "ABC", for "431", it's "134".
    # start from the back
    # if you find a rising edge, all good, if you find a falling edge do this
    # find the next larger element in the right side
    # swap that with current element
    # sort the right side i.e. reverse
    # return the result
    # this way you get all the next lexicographical permutation.
    # [20 30 50 40 38 32]
    # [20 30  |   50 40 38 32]
    # [20 32  |   50 40 38 30]
    # [20 32  |-> 30 38 40 50]
    # If you go through all the vector without this, there are no more permutations left.
    def find_next_largest(self, array: list, start, end) -> int:
        min_element = array[start]
        idx_min = start
        for i in range(start, end):
            if array[i] < min_element:
                min_element = array[i]
                idx_min = i
        return idx_min

    def get_next_permutation(self, string_as_list: list) -> tuple:
        size = len(string_as_list)
        for idx in range(size-1, 0, -1):
            # idx_back = size - idx -1
            if string_as_list[idx-1] < string_as_list[idx]:
                idx_next_largest = self.find_next_largest(string_as_list, idx, size)
                # print(f"indices: {idx-1}, {idx_next_largest}")
                string_as_list[idx-1], string_as_list[idx_next_largest] = string_as_list[idx_next_largest], string_as_list[idx-1]
                p = string_as_list[0: idx] + list(reversed(string_as_list[idx:]))
                return (p, True)
        return ([], False)
        
    def find_permutations(self, string):
        string_as_list = sorted(string.split())
        permutation_exist = True
        res = []
        while permutation_exist:
            p, permutation_exist = self.get_next_permutation(string_as_list)
            if permutation_exist:
                res.append(p)
        return res

    def find_permutations_iter(self, string):
        if string is None:
            return None
        if not string:
            return ""
        p = []
        for i in itertools.permutations(string):
            res = "".join(i)
            if res not in p:
                p.append(res)
        return p
p = Permutations()
string = ["a","b","c"]
for i in range(10):
    new_str, res = p.get_next_permutation(string)
    print(new_str, res)
    string = new_str
# p.find_permutations("AABC")<jupyter_output>['a', 'c', 'b'] True
['b', 'a', 'c'] True
['b', 'c', 'a'] True
['a', 'b', 'c'] True
['a', 'c', 'b'] True
['b', 'a', 'c'] True
['b', 'c', 'a'] True
['a', 'b', 'c'] True
['a', 'c', 'b'] True
['b', 'a', 'c'] True<jupyter_text>Unit Test **The following unit test is expected to fail until you solve the challenge.**<jupyter_code># %load test_permutations.py
import unittest


class TestPermutations(unittest.TestCase):

    def test_permutations(self):
        permutations = Permutations()
        self.assertEqual(permutations.find_permutations(None), None)
        self.assertEqual(permutations.find_permutations(''), '')
        string = 'AABC'
        expected = [
            'AABC', 'AACB', 'ABAC', 'ABCA',
            'ACAB', 'ACBA', 'BAAC', 'BACA',
            'BCAA', 'CAAB', 'CABA', 'CBAA'
        ]
        self.assertCountEqual(permutations.find_permutations(string), expected)
        print('Success: test_permutations')


def main():
    test = TestPermutations()
    test.test_permutations()


if __name__ == '__main__':
    main()<jupyter_output>Success: test_permutations
{'fraction_non_alphanumeric': 0.12736660929432014, 'fraction_numerical': 0.013984509466437178, 'mean_word_length': 2.755250403877221, 'pattern_counts': {'":': 0, '<': 10, '<?xml version=': 0, '>': 14, 'https://': 2, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '2', 'dir': 'jupyter-structured-clean-dedup', 'id': '582602', 'license': 'Apache-2.0', 'n_tokens_mistral': 1577, 'n_tokens_neox': 1465, 'n_words': 455, 'path': 'recursion_dynamic/permutations/permutations_challenge.ipynb', 'repo_name': 'keivanzavari/interactive-coding-challenges', 'size': '4654'}