#include "UniqueNumber.h"

// Use 8-bit Data type for 8-bit MCU's like ATmega328
using DataType = uint8_t;

// Use 32-bit data type for 8-bit MCU's like EPS8266 / ESP32
// using DataType = uint32_t;

const size_t maximumNumber = 99;

UniqueNumber<DataType, maximumNumber> uniqueNumber;


void setup() {
  Serial.begin(115200);

  Serial.print("Generating ");
  Serial.print(maximumNumber);
  Serial.println(" unique random numbers:");

  while (uniqueNumber.available()) {
    Serial.println(uniqueNumber.generateRandomNumber());
  }

  Serial.print("UniqueNumber<DataType, maximumNumber> needs ");
  Serial.print(sizeof(UniqueNumber<DataType, maximumNumber>));
  Serial.print(" bytes of RAM.");
}

void loop() {
}


sketch.ino

diagram.json

#pragma once
#include <Arduino.h>

template <typename T, size_t maximumNumber>
class UniqueNumber {
public:
    UniqueNumber();
    void clear();
    void storeNumber(size_t number);
    bool isStored(size_t number) const;
    size_t findSmallestAvailableNumber() const;
    size_t findLargestAvailableNumber() const;
    size_t generateRandomNumber();
    size_t available() const;
    void dump() const;

protected:
    static const size_t arrayLength = (maximumNumber + (sizeof(T) * 8) - 1) / (sizeof(T) * 8);
    T numbers[arrayLength];
};

template <typename T, size_t maximumNumber>
UniqueNumber<T, maximumNumber>::UniqueNumber() {
    clear();
}

template <typename T, size_t maximumNumber>
void UniqueNumber<T, maximumNumber>::clear() {
    // Initialize the array with zeros
    memset(numbers, 0, sizeof(numbers));
}

template <typename T, size_t maximumNumber>
void UniqueNumber<T, maximumNumber>::storeNumber(size_t number) {
    size_t arrayIndex = number / (sizeof(T) * 8); // Calculation of the index in the array
    size_t bit = number % (sizeof(T) * 8); // Calculation of the index of the bit

    // Set the bit if the number is not 0 or the least significant bit of the least significant element
    if (number != 0 || (bit == 0 && arrayIndex == 0)) {
        numbers[arrayIndex] |= (static_cast<T>(1) << bit);
    }
}

template <typename T, size_t maximumNumber>
bool UniqueNumber<T, maximumNumber>::isStored(size_t number) const {
    size_t arrayIndex = number / (sizeof(T) * 8); // Calculation of the index in the array
    size_t bit = number % (sizeof(T) * 8); // Calculation of the index of the bit

    // Check if the bit is set, except when the number is 0 and the least significant bit of the least significant element
    if (number == 0) {
        return (numbers[0] & 1);
    } else {
        return (numbers[arrayIndex] >> bit) & 1;
    }
}

template <typename T, size_t maximumNumber>
void UniqueNumber<T, maximumNumber>::dump() const {
    for (size_t i = arrayLength; i > 0; --i) {
        for (int j = sizeof(T) * 8 - 1; j >= 0; --j) {
            T bit = (numbers[i - 1] >> j) & 1;
            Serial.print(bit);
        }
        Serial.print(" ");
    }
}

template <typename T, size_t maximumNumber>
size_t UniqueNumber<T, maximumNumber>::findSmallestAvailableNumber() const {
    size_t bitsPerElement = sizeof(T) * 8;

    for (size_t i = 0; i < arrayLength; ++i) {
        for (size_t j = 0; j < bitsPerElement; ++j) {
            size_t number = i * bitsPerElement + j;

            if (!isStored(number)) {
                return number;
            }
        }
    }

    return maximumNumber; // If all numbers are set, then the maximum number is the smallest available number
}

template <typename T, size_t maximumNumber>
size_t UniqueNumber<T, maximumNumber>::available() const {
    size_t availableCount = 0;
    for (size_t i = 0; i <= maximumNumber; ++i) {
        if (!isStored(i)) {
            ++availableCount;
        }
    }
    return availableCount;
}

template <typename T, size_t maximumNumber>
size_t UniqueNumber<T, maximumNumber>::findLargestAvailableNumber() const {
    size_t bitsPerElement = sizeof(T) * 8;

    for (size_t i = arrayLength; i > 0; --i) {
        for (int j = sizeof(T) * 8 - 1; j >= 0; --j) {
            size_t number = (i - 1) * bitsPerElement + j;

            if (number <= maximumNumber && !isStored(number)) {
                return number;
            }
        }
    }
    return maximumNumber; // If all numbers up to maximumNumber are set, then maximumNumber is the largest available number
}

template <typename T, size_t maximumNumber>
size_t UniqueNumber<T, maximumNumber>::generateRandomNumber() {
    if (!available()) {
        return 0; // If no free number is available, return 0
    }

    size_t smallestAvailable = findSmallestAvailableNumber();
    size_t largestAvailable = findLargestAvailableNumber();

    // Generate a random number within the range
    size_t randomNumber = 0;
    do {
        randomNumber = random(smallestAvailable, largestAvailable + 1);
    } while (isStored(randomNumber)); // Check if the random number is already in the bit set

    // Store the random number in the bit set
    storeNumber(randomNumber);

    // Return the random number
    return randomNumber;
}