Sequence Padder

easyFREESequence ProcessingNLP 2: Applications

Given a list of integer sequences, pad all sequences to the length of the longest sequence by appending zeros at the end.

Input: seqs, a list of integer lists (e.g. [[1, 2, 3], [4, 5], [6]]).

Output: A list of padded integer lists, one per input sequence, in the original order. The example below shows each returned sequence printed on its own line.

Example

Input

Output

[1, 2, 3]
[4, 5, 0]
[6, 0, 0]

Reasoning

Input: seqs holds three integer sequences of different lengths: [1, 2, 3] (length 3), $(4, 5)$ (length 2) and $(6)$ (length 1). In NLP these are typically token-ID sequences that must share one length before they can be stacked into a batch.
Target length: the longest sequence sets it, $L = \max(3, 2, 1) = 3$ .
Zeros needed: a sequence of length $\ell$ gets $L - \ell$ zeros appended after its last element: $3 - 3 = 0$ , $3 - 2 = 1$ and $3 - 1 = 2$ .
Output: three sequences, all of length 3: [1, 2, 3] is unchanged, [4, 5, 0] gains one zero, [6, 0, 0] gains two. Together they form a $3 \times 3$ grid.
Notice that the original values stay at the front in their original order, and every zero sits at the end (post-padding). If all inputs already share a length (say two pairs of numbers), nothing is added.

Constraints

1 ≤ n ≤ 10
Sequences can have different lengths
Pad with 0 at the end (post-padding)
Output each sequence as a Python list

More from NLP 2: Applications

BIO Entity Span Extractoreasy Simple Entity Taggereasy Sentiment Word Countereasy Keyword Classifiereasy One-Hot Sequence Encodereasy

Concept primer

Background Knowledge

The "Sequence Padder" problem falls under the category of sequence processing, a fundamental concept in Natural Language Processing (NLP) and other areas of computer science. Sequence processing involves handling and manipulating sequences of data, such as strings, lists, or arrays. In NLP, sequences often represent text data, like sentences or documents, where each element in the sequence corresponds to a word or token. Understanding how to process and transform sequences is crucial for various NLP tasks, including text classification, language modeling, and machine translation.

In the context of this problem, we're dealing with sequences of integers, which can be thought of as a simplified representation of text data. The goal is to pad these sequences to a uniform length by appending zeros, ensuring that all sequences have the same number of elements. This technique is commonly used in deep learning and machine learning applications, where input data often needs to be standardized before being fed into a model. By padding sequences, we can ensure that our models receive input data with a consistent structure, which is essential for training and making predictions.

The concept of padding sequences is closely related to the idea of tokenization, where text data is split into individual tokens or elements. In this case, our sequences are already tokenized, and we need to adjust their lengths to create a consistent input format. This process requires understanding of basic data structures, such as lists or arrays, and how to manipulate them using programming languages.

Algorithm/Approach

The general approach to solving this problem involves a simple iterative strategy, where we iterate over each sequence, determine its length, and append zeros as needed to reach the desired length. This approach can be broken down into several key steps, including reading input data, finding the maximum sequence length, and padding each sequence accordingly.

Step-by-Step Strategy

To implement the solution, follow these steps:

Read the number of sequences n from the input.
Initialize an empty list to store the sequences.
Iterate over each sequence, reading the space-separated integers and storing them in a list.
Keep track of the maximum sequence length encountered so far.
Once all sequences are read, iterate over each sequence again and append zeros as needed to reach the maximum length.
Output each padded sequence as a list.

Common Pitfalls

When implementing the solution, watch out for the following common pitfalls:

Forgetting to initialize variables or data structures before using them.
Incorrectly handling the input data, such as assuming a fixed sequence length or failing to account for zero-length sequences.
Not properly appending zeros to the sequences, resulting in incorrect output.

Time & Space Complexity

The expected time complexity for this problem is O(n * m), where n is the number of sequences and m is the maximum sequence length. This is because we need to iterate over each sequence and potentially append zeros to each one. The space complexity is also O(n * m), as we need to store all the padded sequences in memory.

solution.py

Python 3.13

Test results