UPDATED

The NLTK version 3.2.5 now includes the skipgrams function.

Check out a cleaner implementation by @jnothman on the NLTK repository: https://github.com/nltk/nltk/blob/develop/nltk/util.py#L538

def skipgrams(sequence, n, k, **kwargs):
    """
    This function generates all possible skipgrams from a sequence with specified parameters.
    Skipgrams are essentially n-grams that allow tokens to be skipped.
    Reference: http://homepages.inf.ed.ac.uk/ballison/pdf/lrec_skipgrams.pdf
    Parameters:
    - sequence: input data for generating skipgrams
    - n: degree of the n-grams
    - k: skip distance between tokens
    Return type: iterator yielding tuples
    """

    # Pad sequence based on kwargs if required.
    if 'pad_left' in kwargs or 'pad_right' in kwargs:
    sequence = pad_sequence(sequence, n, **kwargs)

    SENTINEL = object()  # Stop sentinel used during iteration.
    for ngram in ngrams(sequence, n + k, pad_right=True, right_pad_symbol=SENTINEL):
    head = ngram[:1]
    tail = ngram[1:]
    for skip_tail in combinations(tail, n - 1):
        if skip_tail[-1] is SENTINEL:
            continue
        yield head + skip_tail

[out]:

>>> from nltk.util import skipgrams
>>> sent = "Insurgents killed in ongoing fighting".split()
>>> list(skipgrams(sent, 2, 2))
[('Insurgents', 'killed'), ('Insurgents', 'in'), ('Insurgents', 'ongoing'), ('killed', 'in'), ('killed', 'ongoing'), ('killed', 'fighting'), ('in', 'ongoing'), ('in', 'fighting'), ('ongoing', 'fighting')]
>>> list(skipgrams(sent, 3, 2))
[('Insurgents', 'killed', 'in'), ('Insurgents', 'killed', 'ongoing'), ('Insurgents', 'killed', 'fighting'), ('Insurgents', 'in', 'ongoing'), ('Insurgents', 'in', 'fighting'), ('Insurgents', 'ongoing', 'fighting'), ('killed', 'in', 'ongoing'), ('killed', 'in', 'fighting'), ('killed', 'ongoing', 'fighting'), ('in', 'ongoing', 'fighting')]

Embarking on a different path from your current code and opting for an external library, you can utilize Colibri Core () for efficient skipgram extraction. This library is designed specifically for extracting n-grams and skipgrams swiftly from large text corpora. While the underlying code is in C++ for performance reasons, there is also a Python binding available.

You rightly highlighted the importance of efficiency, especially when dealing with skipgram extraction that can exhibit exponential complexity. This may not be concerning if you are processing just one sentence as demonstrated in your input_list, but it could pose challenges when working with extensive corpus data. To address this, setting parameters like an occurrence threshold or requiring each skip to be filled by at least x distinct n-grams can help mitigate the issue.

import colibricore

#Prepare the corpus data (will be encoded for efficiency)
corpusfile_plaintext = "somecorpus.txt" #input file with one sentence per line
encoder = colibricore.ClassEncoder()
encoder.build(corpusfile_plaintext)
corpusfile = "somecorpus.colibri.dat" #output corpus file
classfile = "somecorpus.colibri.cls" #output of class encoding
encoder.encodefile(corpusfile_plaintext,corpusfile)
encoder.save(classfile)

#Specify options for skipgram extraction (mintokens defines the occurrence threshold, maxlength sets the maximum ngram/skipgram length)
options = colibricore.PatternModelOptions(mintokens=2,maxlength=8,doskipgrams=True) 

#Create an empty pattern model 
model = colibricore.UnindexedPatternModel()

#Train the model using the encoded corpus file (this triggers skipgram extraction)
model.train(corpusfile, options)

#Load a decoder to view the output
decoder = colibricore.ClassDecoder(classfile)

#Display all skipgrams
for pattern in model:
     if pattern.category() == colibricore.Category.SKIPGRAM:
         print(pattern.tostring(decoder))

A more detailed Python tutorial covering these processes is available on the website.

Disclaimer: I am the developer of Colibri Core

For a comprehensive understanding, please check out this link.

The example provided below illustrates how this function can be utilized effectively.

>>>sent = "Insurgents killed in ongoing fighting".split()
>>>list(skipgrams(sent, 2, 2))
[('Insurgents', 'killed'), ('Insurgents', 'in'), ('Insurgents', 'ongoing'), ('killed', 'in'), ('killed', 'ongoing'), ('killed', 'fighting'), ('in', 'ongoing'), ('in', 'fighting'), ('ongoing', 'fighting')]

Why not consider utilizing an existing implementation from someone else, found at https://github.com/heaven00/skipgram/blob/master/skipgram.py, where k = skip_size and n=ngram_order:

def skipgram_ndarray(sent, k=1, n=2):
    """
    This is not exactly a vectorized version, because we are still
    using a for loop
    """
    tokens = sent.split()
    if len(tokens) < k + 2:
        raise Exception("REQ: length of sentence > skip + 2")
    matrix = np.zeros((len(tokens), k + 2), dtype=object)
    matrix[:, 0] = tokens
    matrix[:, 1] = tokens[1:] + ['']
    result = []
    for skip in range(1, k + 1):
        matrix[:, skip + 1] = tokens[skip + 1:] + [''] * (skip + 1)
    for index in range(1, k + 2):
        temp = matrix[:, 0] + ',' + matrix[:, index]
        map(result.append, temp.tolist())
    limit = (((k + 1) * (k + 2)) / 6) * ((3 * n) - (2 * k) - 6)
    return result[:limit]

def skipgram_list(sent, k=1, n=2):
    """
    Form skipgram features using list comprehensions
    """
    tokens = sent.split()
    tokens_n = ['''tokens[index + j + {0}]'''.format(index)
                for index in range(n - 1)]
    x = '(tokens[index], ' + ', '.join(tokens_n) + ')'
    query_part1 = 'result = [' + x + ' for index in range(len(tokens))'
    query_part2 = ' for j in range(1, k+2) if index + j + n < len(tokens)]'
    exec(query_part1 + query_part2)
    return result