Как найти позицию из индекса комбинации - PullRequest
Новая
       13

Как найти позицию из индекса комбинации

0 голосов
/ 15 октября 2018

Пожалуйста, потерпите меня, пока я пытаюсь объяснить, чего я хотел бы достичь.У меня есть конфигурация из n терминов.Каждый член в этой конфигурации может иметь любое количество элементов, которые отличаются друг от друга.Например: 

term1 = ["hello", "greetings", "heya"] // 3 elements
term2 = ["is", "are", "you", "wow"] // 4 elements
term3 = ["doing", "now"] // 2 elements

Как видите, каждый член имеет разное количество элементов.Я могу рассчитать общее количество комбинаций, выполнив: 

totalSize = term1.size * term2.size * term3.size

Я хотел бы иметь возможность автоматически получить конфигурацию, указав позицию.Скажем, у меня есть в общей сложности 1000 возможных комбинаций, я хотел бы узнать, какую комбинацию терминов получит позиция 500.

Прямо сейчас я перебираю все это, чтобы добраться до этой позиции;это неэффективно.

Будем весьма признательны за любые предложения или идеи,

Спасибо за потраченное время.

1 Ответ

0 голосов
/ 15 октября 2018

Чтобы осмысленно присвоить номер каждой комбинации, нужно выбрать схему заказа.Поскольку существует много комбинаций, и каждый действительный порядок является просто перестановкой каждой возможной комбинации, существует множество возможных способов упорядочить такие комбинации.Один из возможных заказов может работать следующим образом:

Входные данные: список из трех строк s1, s2 и s3, каждая из которых содержит соответственно term1, term2 и term3.

Выходные данные: уникальное целое число от 0 до 23 или размеры term1, term2 иумножение term3.

  • set x = 0
  • term1:
    • , если s1 = "привет", добавить 0 к x
    • , если s1 ="привет", добавьте 1 к x
    • , если s1 = "heya", добавьте 2 к x
  • term2:
    • , умножьте x на 3,размер term1
    • , если s2 = "is", добавить 0 к x
    • , если s2 = "are", добавить 1 к x
    • , если s2 = "you", добавьте 2 к x
    • , если s2 = "вау", добавьте 3 к x
  • term3:
    • умножьте x на 4, размерterm2
    • если x = "делает", добавьте 0 к x
    • , если x = "сейчас", добавьте 1 к x
  • return x

Создать список строк из term1, term2 и term3 из заданного числа - это просто обратная задача этой проблемы.Вот описание такого алгоритма:

Входные данные: число x

Выходные данные: тройка строк s1, s2 и s3, каждая из которых содержит соответственно term1, term2 и term3

  • s3:
    • let i = x mod 2, размер term3
    • set s3 = term3 [i]
    • set x = (x - i) / 2
  • s2:
    • let i = x mod 4, размер term2
    • set s2 = term2 [i]
    • set x = (x - 1)/ 4
  • s1:
    • let i = x mod 3, размер term1
    • set s3 = term1 [i]
  • возврат (s1, s2, s3)

Очевидно, это довольно просто реализовать.Я сделаю вам и будущим читателям услугу, написав обобщенную версию, которая принимает любое количество массивов строк.Обратите внимание, что эти термины используются в обратном порядке из приведенного выше описания, но при этом генерируется уникальный список для каждого номера. 

vector<string> getCombination(const vector<vector<string>>& terms, long x){
    vector<string> result;
    for (const auto& term : terms){
        const long i = x % term.size();
        result.push_back(term[i]);
        x = (x - i) / term.size();
    }
    return result;
}

Пример использования: 

vector<vector<string>> terms {
    {"hello", "greetings", "heya"},
    {"is", "are", "you", "wow"},
    {"doing", "now"}
};

getCombination(terms, 0);  // -> hello is doing
getCombination(terms, 1);  // -> greetings is doing
getCombination(terms, 2);  // -> heya is doing
...
getCombination(terms, 12); // -> hello is now
...
getCombination(terms, 22); // -> greetings wow now
getCombination(terms, 23); // -> heya wow now
...