Python - restructuring a list to only increase in increments of 1

The self-referential defaultdict trick in another (simpler & more efficient) way:

from collections import defaultdict

values = [1827, 1827, 1829, 1829, 1827, 1827, 1833]

d = defaultdict(lambda: len(d) + values[0])

[d[v] for v in values]
# [1827, 1827, 1828, 1828, 1827, 1827, 1829]

This can be done elegantly with a defaultdict and a good lambda:

from collections import defaultdict

values = [1827, 1827, 1829, 1829, 1827, 1827, 1833]

d = defaultdict(lambda: max(list(d.values()) + [min(values) - 1]) + 1)
[d[value] for value in values]

[1827, 1827, 1828, 1828, 1827, 1827, 1829]

This works because we're binding the dictionary itself into the lambda it uses for setting the value of a missing key. We can max those values and figure out the right value.

We need to start the dictionary off with the lowest value in the list (alternatively you can start it off with the first value in the list with values[0])

I profiled the solutions:

import random
from collections import defaultdict


def max_defaultdict(values):
    # @swozny
    d = defaultdict(lambda: max(list(d.values()) + [min(values) - 1]) + 1)
    [d[value] for value in values]


def len_defaultdict(values):
    # @user2390182
    d = defaultdict(lambda: len(d) + values[0])
    [d[v] for v in values]


def dictionary_approach(contact_ids):
    # @John Coleman
    start = contact_ids[0]
    rank = 0
    ranks = {}
    for contact_id in contact_ids:
        if contact_id not in ranks:
            ranks[contact_id] = rank
            rank += 1

    output = [start + ranks[contact_id] for contact_id in contact_ids]


def setup(N):
    values = [1827]
    for _ in range(N - 1):
        next_value = values[-1] + random.randint(-2, 2)
        values.append(max(next_value, 1827))
    return [values]


from performance_measurement import run_performance_comparison

approaches = [dictionary_approach, len_defaultdict, max_defaultdict]
run_performance_comparison(
    approaches, [10_000, 20_000, 30_000, 100_000, 200_000], setup=setup
)

The repeated max calls really put this solution far behind the dictionary solution. What's interesting is that the len based defaultdict beats even the dictionary.

Profiling Code

import timeit
from functools import partial

from typing import List, Dict, Callable

from contextlib import contextmanager
import matplotlib.pyplot as plt


@contextmanager
def data_provider(data_size, setup=lambda N: N, teardown=lambda: None):
    data = setup(data_size)
    yield data
    teardown(*data)


def run_performance_comparison(approaches: List[Callable],
                               data_size: List[int],
                               *,
                               setup=lambda N: [N],
                               teardown=lambda *N: None,
                               number_of_repetitions=5,
                               title='Performance Comparison',
                               data_name='N',
                               yscale='log',
                               xscale='log'):
    approach_times: Dict[Callable, List[float]] = {approach: [] for approach in approaches}
    for N in data_size:
        with data_provider(N, setup, teardown) as data:
            print(f'Running performance comparison for {data_name}={N}')
            for approach in approaches:
                function = partial(approach, *data)
                approach_time = min(timeit.Timer(function).repeat(repeat=number_of_repetitions, number=1))
                approach_times[approach].append(approach_time)

    for approach in approaches:
        plt.plot(data_size, approach_times[approach], label=approach.__name__)
    plt.yscale(yscale)
    plt.xscale(xscale)

    plt.xlabel(data_name)
    plt.ylabel('Execution Time (seconds)')
    plt.title(title)
    plt.legend()
    plt.show()

Define the rank of a contact id to be its index in the list of contact ids with duplicates removed. These are the offsets from the start in the intended output. They can be obtained in various ways. The following code does so using a dictionary, which is then used in a list comprehension to get the final output:

contact_ids = [1827, 1827, 1829, 1829, 1827, 1827, 1833]
start = contact_ids[0]
rank = 0
ranks = {}
for contact_id in contact_ids:
  if contact_id not in ranks:
    ranks[contact_id] = rank
    rank += 1

output = [start + ranks[contact_id] for contact_id in contact_ids]
print(output)
#[1827, 1827, 1828, 1828, 1827, 1827, 1829]

Based on the statement that non-repeated numbers can be identified as being equal to their offset from the first one, you could can determine where the +1 increment should occur. Then use itertools.accumulate to compute the total increment to apply to each position (from the base) and replace the larger values with it:

from itertools import accumulate

values = [1827, 1827, 1829, 1829, 1827, 1827, 1833]

inc      = accumulate( p if p == values[0] else p == n
                       for p,n in enumerate(values,values[0]))
*output, = map(min, zip(values,inc)) 

print(output)
[1827, 1827, 1828, 1828, 1827, 1827, 1829]