Skip to content

foapy.order

order(X, return_alphabet=False)

Decompose an array into an order and an alphabet.

Alphabet is a list of all unique values from the input array in order of their first appearance. Order is an array of indices that maps each element in the input array to its position in the alphabet.

Input array X Order Alphabet Note
[ x y x z ] [ 0 1 0 2 ] [ x y z ] Example decomposition into order and alphabet
[ y x y z ] [ 0 1 0 2 ] [ y x z ] Same order as above, different alphabet
[ y y x z ] [ 0 0 1 2 ] [ y x z ] Same alphabet as above, different order
[ ] [ ] [ ] Empty array

Parameters:

Name Type Description Default

X

array_like

Array to decompose into an order and an alphabet. Must be a 1-dimensional array.

 required

return_alphabet

bool

If True also return array's alphabet

 False

Returns:

Name Type Description
order ndarray

Order of X
alphabet ndarray

Alphabet of X. Only provided if return_alphabet is True.

Raises:

Type Description
Not1DArrayException

When X parameter is not d1 array

Examples:

Get an order of a characters sequence.

1
2
3
4
5
import foapy
source = ['a', 'b', 'a', 'c', 'd']
order = foapy.order(source)
print(order)
# [0, 1, 0, 2, 3]

Reconstruct original sequence from the order and the alphabet.

1
2
3
4
5
6
7
8
import foapy
source = ['a', 'c', 'c', 'e', 'd', 'a']
order, alphabet = foapy.order(source, True)
print(order, alphabet)
# [0, 1, 1, 2, 3, 0] ['a', 'c', 'e', 'd']
restored = alphabet[order]
print(restored)
# ['a', 'c', 'c', 'e', 'd', 'a']

An order of an empty sequence is empty array.

1
2
3
4
5
import foapy
source = []
order = foapy.order(source)
print(order)
# []

Getting an order of an array with more than 1 dimension is not allowed

1
2
3
4
import foapy
source = [[[1], [3]], [[6], [9]], [[6], [3]]]
order = foapy.order(source)
# Not1DArrayException: {'message': 'Incorrect array form. Expected d1 array, exists 3'}
Source code in .tox/docs-deploy/lib/python3.11/site-packages/foapy/core/_order.py 
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
def order(X, return_alphabet: bool = False) -> ndarray:
    """

    Decompose an array into an order and an alphabet.

    Alphabet is a list of all unique values from the input array in order of their first appearance.
    Order is an array of indices that maps each element in the input array to its position
    in the alphabet.

    | Input array X | Order       | Alphabet  | Note                                              |
    |---------------|-------------|-----------|---------------------------------------------------|
    | [ x y x z ]   | [ 0 1 0 2 ] | [ x y z ] | Example decomposition into order and alphabet     |
    | [ y x y z ]   | [ 0 1 0 2 ] | [ y x z ] | Same order as above, different alphabet           |
    | [ y y x z ]   | [ 0 0 1 2 ] | [ y x z ] | Same alphabet as above, different order           |
    | [ ]           | [ ]         | [ ]       | Empty array                                       |

    Parameters
    ----------
    X : np.array_like
        Array to decompose into an order and an alphabet. Must be a 1-dimensional array.

    return_alphabet : bool, optional
        If True also return array's alphabet

    Returns
    -------
    order : ndarray
        Order of X

    alphabet : ndarray
        Alphabet of X. Only provided if `return_alphabet` is True.

    Raises
    -------
    Not1DArrayException
        When X parameter is not d1 array

    Examples
    --------

    Get an order of a characters sequence.

    ``` py linenums="1"
    import foapy
    source = ['a', 'b', 'a', 'c', 'd']
    order = foapy.order(source)
    print(order)
    # [0, 1, 0, 2, 3]
    ```

    Reconstruct original sequence from the order and the alphabet.

    ``` py linenums="1"
    import foapy
    source = ['a', 'c', 'c', 'e', 'd', 'a']
    order, alphabet = foapy.order(source, True)
    print(order, alphabet)
    # [0, 1, 1, 2, 3, 0] ['a', 'c', 'e', 'd']
    restored = alphabet[order]
    print(restored)
    # ['a', 'c', 'c', 'e', 'd', 'a']
    ```

    An order of an empty sequence is empty array.

    ``` py linenums="1"
    import foapy
    source = []
    order = foapy.order(source)
    print(order)
    # []
    ```

    Getting an order of an array with more than 1 dimension is not allowed

    ``` py linenums="1"
    import foapy
    source = [[[1], [3]], [[6], [9]], [[6], [3]]]
    order = foapy.order(source)
    # Not1DArrayException: {'message': 'Incorrect array form. Expected d1 array, exists 3'}
    ```
    """  # noqa: E501

    data = np.asanyarray(X)
    if data.ndim > 1:  # Checking for d1 array
        raise Not1DArrayException(
            {"message": f"Incorrect array form. Expected d1 array, exists {data.ndim}"}
        )

    perm = data.argsort(kind="mergesort")

    unique_mask = np.empty(data.shape, dtype=bool)
    unique_mask[:1] = True
    unique_mask[1:] = data[perm[1:]] != data[perm[:-1]]

    result_mask = np.zeros_like(unique_mask)
    result_mask[:1] = True
    result_mask[perm[unique_mask]] = True

    power = np.count_nonzero(unique_mask)

    inverse_perm = np.empty(data.shape, dtype=np.intp)
    inverse_perm[perm] = np.arange(data.shape[0])

    result = np.cumsum(unique_mask) - 1
    inverse_alphabet_perm = np.empty(power, dtype=np.intp)
    inverse_alphabet_perm[result[inverse_perm][result_mask]] = np.arange(power)

    result = inverse_alphabet_perm[result][inverse_perm]

    if return_alphabet:
        return result, data[result_mask]
    return result