<commit_before>
class Permutation(object):
    """Base Permutation object"""
    def __init__(self, perm, check=False):
        """Create a new Permutation from the given list.
        If check, then check that the permutation is of the correct form"""
        if check:
            assert type(perm) is list
            n = len(perm)
            used = [False]*n

            for x in perm:
                assert type(x) is int
                assert 1 <= x <= n
                assert not used[x-1]
                used[x-1] = True

        self.perm = list(perm)

    def contains(self, pattern):
        """Returns true if permutation self contains a given pattern"""
        if type(pattern) is list:
            pattern = Permutation(pattern)
        return pattern.contained_in(self)

    def avoids(self, pattern):
        """Returns True if self contains no occurrence of pattern"""
        if type(pattern) is list and all( type(patt) is list or type(patt) is Permutation for patt in pattern ):
            for patt in pattern:
                if self.contains(patt):
                    return False
            return True

        return not self.contains(pattern)

    def contained_in(self, perm):
        """Returns true if the permutation self is contained in the
        permutation perm.
        self is treated as a pattern"""
        return any( True for _ in self.occurrences_in(perm) )

    def count_occurrences_in(self, perm):
        """Count the number of occurrences of the pattern self in the permutation perm."""
        return sum(1 for _ in self.occurrences_in(perm))

    def count_occurrences_of(self, patt):
        """Count the number of occurrences of the pattern patt in the permutation self."""
        return patt.count_occurrences_in(self)

    def occurrences_in(self, perm):
        """Find all indices of occurrences of self in perm.
        
        Args:
            self:
                The classical pattern whose occurrences are to be found.
            perm: permuta.Permutation
                The permutation to search for occurrences in.

        Yields: [int]
            Each yielded element l is a list of integer indices of the
            permutation perm such that:
            self == permuta.Permutation.to_standard([perm[i] for i in l])
        """

        # Calculate all prefix flattenings of the pattern self
        k_standard_patt = [Permutation.to_standard(self[:k]).perm for k in range(0, len(self))]
        k_standard_patt.append(self.perm)

        # These two lists define a pattern in the permutation perm
        # occurrence is the actual elements and indices is their indices in perm
        occurrence = [None]*len(self)
        indices = occurrence[:]

        # Define function that works with the above defined variables
        # i is the index of the element in perm that is to be considered
        # k is how many elements of the permutation have already been added to occurrence
        # flattened is the flattened occurrence so far
        def con(i, k, flattened):

            # Length of the occurrence has reached length of pattern
            if k == len(self):
                yield indices[:]
                return

            elements_left = len(perm) - i
            elements_needed = len(self) - k
            if elements_left < elements_needed:
                # Not enough elements left to make occurrence
                return
            elif elements_left == elements_needed:
                # Enough elements left to make a single occurrence
                # Add them all
                while i < len(perm):
                    Permutation._add_to_flattened(perm, flattened, indices, i)
                    #occurrence[k] = perm[i]  # Unnecessary
                    indices[k] = i
                    k += 1
                    i += 1
                if flattened == self.perm:
                    yield indices[:]
                return

            # Incrementally build flattened occurrence
            new_flattened = flattened[:]
            Permutation._add_to_flattened(perm, new_flattened, indices, i)

            # Yield occurrences where the ith element is chosen
            if new_flattened == k_standard_patt[k+1]:
                # Still conforms to pattern,
                # so add index and element and look further
                occurrence[k] = perm[i]
                indices[k] = i
                for o in con(i+1, k+1, new_flattened):
                    yield o

            # Yield occurrences where the ith element is not chosen
            for o in con(i+1, k, flattened):
                yield o

        for o in con(0, 0, []):
            yield o

    def occurrences_of(self, patt):
        """Find all indices of occurrences of patt in self.

        This method is complementary to permuta.Permutation.occurrences_in
        It just calls patt.occurrences_in(self) internally.
        See permuta.Permutation.occurrences_in for documentation.
        """
        return patt.occurrences_in(self)

    @staticmethod
    def _add_to_flattened(perm, flattened, indices, index_of_new):
        """Single step of online flattening of permutation.

        Args:
            perm: permuta.Permutation
                The permutation the rest of the arguments refer to.
            flattened: [int]
                The flattened list of [perm[i] for i in indices[:len(flattened)]].
                The function modifies this list.
            indices: [int]
                The indices of the elements in perm that have been flattened.
                Only the first len(flattened) are legitimate.
            index_of_new: int
                The index of the perm element to be added to the flattened list.
        Returns: None
            The flattened argument is modified and nothing is returned.
        """
        not_incremented_counter = 0
        new_element = perm[index_of_new]
        for i in range(len(flattened)):
            if perm[indices[i]] > new_element:
                flattened[i] += 1
            else:
                not_incremented_counter += 1
        new_element_flattened = 1 + not_incremented_counter
        flattened.append(new_element_flattened)
        return<commit_msg>Prefix flattenings calculated incrementally as well, seems to be slightly faster<commit_after>
class Permutation(object):
    """Base Permutation object"""
    def __init__(self, perm, check=False):
        """Create a new Permutation from the given list.
        If check, then check that the permutation is of the correct form"""
        if check:
            assert type(perm) is list
            n = len(perm)
            used = [False]*n

            for x in perm:
                assert type(x) is int
                assert 1 <= x <= n
                assert not used[x-1]
                used[x-1] = True

        self.perm = list(perm)

    def contains(self, pattern):
        """Returns true if permutation self contains a given pattern"""
        if type(pattern) is list:
            pattern = Permutation(pattern)
        return pattern.contained_in(self)

    def avoids(self, pattern):
        """Returns True if self contains no occurrence of pattern"""
        if type(pattern) is list and all( type(patt) is list or type(patt) is Permutation for patt in pattern ):
            for patt in pattern:
                if self.contains(patt):
                    return False
            return True

        return not self.contains(pattern)

    def contained_in(self, perm):
        """Returns true if the permutation self is contained in the
        permutation perm.
        self is treated as a pattern"""
        return any( True for _ in self.occurrences_in(perm) )

    def count_occurrences_in(self, perm):
        """Count the number of occurrences of the pattern self in the permutation perm."""
        return sum(1 for _ in self.occurrences_in(perm))

    def count_occurrences_of(self, patt):
        """Count the number of occurrences of the pattern patt in the permutation self."""
        return patt.count_occurrences_in(self)

    def occurrences_in(self, perm):
        """Find all indices of occurrences of self in perm.
        
        Args:
            self:
                The classical pattern whose occurrences are to be found.
            perm: permuta.Permutation
                The permutation to search for occurrences in.

        Yields: [int]
            Each yielded element l is a list of integer indices of the
            permutation perm such that:
            self == permuta.Permutation.to_standard([perm[i] for i in l])
        """

        # Calculate all prefix flattenings of the pattern self
        k_standard_patt = [[]]  # First prefix is empty prefix
        patt_indices = range(len(self))  # Indices for online flattening
        i = 1  # Prefix flattenings already calculated
        while i < len(self):
            new = k_standard_patt[-1][:]
            Permutation._online_flattening_step(self.perm, new, patt_indices, i-1)
            k_standard_patt.append(new)
            i += 1
        if len(self) != 0:
            k_standard_patt.append(self.perm)

        # These two lists define a pattern in the permutation perm
        # occurrence is the actual elements and indices is their indices in perm
        #occurrence = [None]*len(self)  # Unnecessary
        indices = [None]*len(self)

        # Define function that works with the above defined variables
        # i is the index of the element in perm that is to be considered
        # k is how many elements of the permutation have already been added to occurrence
        # flattened is the flattened occurrence so far
        def con(i, k, flattened):

            # Length of the occurrence has reached length of pattern
            if k == len(self):
                yield indices[:]
                return

            elements_left = len(perm) - i
            elements_needed = len(self) - k
            if elements_left < elements_needed:
                # Not enough elements left to make occurrence
                return
            elif elements_left == elements_needed:
                # Enough elements left to make a single occurrence
                # Add them all
                while i < len(perm):
                    Permutation._online_flattening_step(perm, flattened, indices, i)
                    #occurrence[k] = perm[i]  # Unnecessary
                    indices[k] = i
                    k += 1
                    i += 1
                if flattened == self.perm:
                    yield indices[:]
                return

            # Incrementally build flattened occurrence
            new_flattened = flattened[:]
            Permutation._online_flattening_step(perm, new_flattened, indices, i)

            # Yield occurrences where the ith element is chosen
            if new_flattened == k_standard_patt[k+1]:
                # Still conforms to pattern,
                # so add index and element and look further
                #occurrence[k] = perm[i]  # Unnecessary
                indices[k] = i
                for o in con(i+1, k+1, new_flattened):
                    yield o

            # Yield occurrences where the ith element is not chosen
            for o in con(i+1, k, flattened):
                yield o

        for o in con(0, 0, []):
            yield o

    def occurrences_of(self, patt):
        """Find all indices of occurrences of patt in self.

        This method is complementary to permuta.Permutation.occurrences_in
        It just calls patt.occurrences_in(self) internally.
        See permuta.Permutation.occurrences_in for documentation.
        """
        return patt.occurrences_in(self)

    @staticmethod
    def _online_flattening_step(perm, flattened, indices, index_of_new):
        """Single step of online flattening of permutation.

        Args:
            perm: permuta.Permutation
                The permutation the rest of the arguments refer to.
            flattened: [int]
                The flattened list of [perm[i] for i in indices[:len(flattened)]].
                The function modifies this list.
            indices: [int]
                The indices of the elements in perm that have been flattened.
                Only the first len(flattened) are legitimate.
            index_of_new: int
                The index of the perm element to be added to the flattened list.
        Returns: None
            The flattened argument is modified and nothing is returned.
        """
        not_incremented_counter = 0
        new_element = perm[index_of_new]
        for i in range(len(flattened)):
            if perm[indices[i]] > new_element:
                flattened[i] += 1
            else:
                not_incremented_counter += 1
        new_element_flattened = 1 + not_incremented_counter
        flattened.append(new_element_flattened)
        return
{'fraction_non_alphanumeric': 0.06705246913580247, 'fraction_numerical': 0.002932098765432099, 'mean_word_length': 1.812106747667607, 'pattern_counts': {'":': 0, '<': 12, '<?xml version=': 0, '>': 5, 'https://': 0, '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}}
{'dir': 'git-commits-cleaned', 'id': '476653', 'n_tokens_mistral': 3568, 'n_tokens_neox': 3173, 'n_words': 1249}