Перебор всех комбинаций элементов из заданных n множеств

#java #cpp #алгоритм #комбинаторика #множества

Как можно сгенерировать все возможные комбинации, состоящие из элементов заданных
n множеств ? Например, если имеется 3 множества:

A=1,2,3,4,...
B=a,b,c,d,...
C=A,B,C,D,...


и нужно получить что-то вроде:

1 a A; 
1 b A; 
1 c A
....
1 a B; 
1 b B


При этом число n заранее неизвестно, так что вложенными циклами решить не получается.
    

Ответы

Ответ 1

Представьте себе, что это - цифры, стоящие на соответствующих местах числа.

Создаем первое число - 1aA (или сколько там нужно мест). Потом просто увеличиваем
последний элемент, пока не переберем все. После этого выставляем его равным минимальному
элементу и увеличиваем предыдущий (если он тоже максимален - сбрасываем его в минимум
и переходим к предыдущему).

1aA
1aB
1aC  // достигли максимума в последней позиции. переход-
1bA
1bB
1bC  // достигли максимума в последней позиции. переход-
1bA
1bB
1bC  // достигли максимума в последней позиции. переход-
1bA
1bB
1bC  // достигли максимума в последней позиции. переход-
1сA
1сB
1сC  // достигли максимума в последней позиции. переход- но во второй позиции
     // тоже максимум, перенос далее
2aA
...


Словом, просто реализуем алгоритм M (Генерация в смешанной позиционной системе счисления)
со страницы 330 4А тома "Искусства программирования"...

Множества как индекс в массиве C++

#множества #строки #cpp

Имеется следующий код:
enum colors { red,green,blue };//дано множество 
int myArray[colors::blue];//и массив
string strColor="Red";//Далее пользователь вводит строку, например

Точно помню, что в паскале можно было провернуть что-то вроде этого: 
myArray[strColor]=...;
    

Ответы

Ответ 1

В C++ так нельзя. Соответственно, нужно городить либо хардкод на условиях, либо пользоваться
промежуточным словарем map.


Ответ 2

Используйте прослойку для преобразования string -> enum.

Например так:

enum colors { red, green, blue }

colors colorFromString(const std::string& str)
{
    static const std::map allColors
    {
        { "red",   colors::red   },
        { "green", colors::green },
        { "blue",  colors::blue  }
    };

    auto founded = allColors.find(str);
    if (founded == allColors.cend())
    {
        // Элемент не найден
        // Здесь необходимо как-то обработать ошибку
        // Например:
        throw std::runtime_error("Not found element " + str);
    }

    return founded->second;
}


Дальше можете делать так, как вы и хотели:

std::string strColor = "red";
myArray[colorFromString(strColor)]=...;


PS: Если будете использовать исключения - не забывайте их перехватывать.

Как удалять один элемент из multiset, если в контейнере имеются дубликаты?

#cpp #stl #множества #multiset

При использовании метода erase() из мультимножества удаляются все элементы со значением
параметра. Можно, конечно, класть в контейнер пару, где first - номер элемента, second
- нужное значение, тогда дубликатов не будет. 

Но есть ли другое решение проблемы? 

Код:

#include 
#include 

using namespace std;

int main()
{
    multiset a = {1, 1, 3};

    for(int i: a)
        cout << i << " "; // Вывод: 1 1 3

    a.erase(1);

    cout << "\n";
    for(int i: a)
        cout << i << " "; // Вывод: 3

    return 0;
}

    

Ответы

Ответ 1

Работайте с итератором. Находите нужный вам элемент, вернее, ненужный :), вернее,
итератор, указывающий на него - и вызывайте erase.

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


Ответ 2

Если вам нужно удалить один элемент, делайте erase(find(key)) вместо erase(key).
Разумеется, в варианте erase(find(key)) надо добавить проверку на успешность поиска.

Однако такой способ удалит "какой-то" из эквивалентных элементов. А уж как вы предлагаете
выбирать конкретный элемент для удаления и нужно ли вам его выбирать - об этом вы пока
не удосужились сообщить.

Зачем и в каких конкретно случаях нужно использовать HashMap, если мы можем сделать тоже самое используя HashSet?

#java #map #коллекции #множества

Есть простой класс:

public class Person {
    private int age;
    private String name;

    public Person(int age, String name) {
        this.age = age;
        this.name = name;
    }

    public int getAge() {
        return age;
    }

    public void setAge(int age) {
        this.age = age;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    @Override
    public String toString() {
        return "Person [age=" + age + ", name=" + name + "]";
    }

}


Есть еще один класс:

public class Item {
    private K key;
    private P person;
    public Item(K key, P person) {
        this.key = key;
        this.person = person;
    }
    public K getKey() {
        return key;
    }
    public void setKey(K key) {
        this.key = key;
    }
    public P getPerson() {
        return person;
    }
    public void setPerson(P person) {
        this.person = person;
    }
    @Override
    public String toString() {
        return "Item [key=" + key + ", person=" + person + "]";
    }


}


ГДЕ ПРАВДА???

И сама реализация классов:

public class Main {
    public static void main(String[] args) {

        Set> set = new HashSet>();

        set.add(new Item(1, new Person(23, "gogo")));
        set.add(new Item(2, new Person(42, "niko")));
        set.add(new Item(3, new Person(32, "toto")));

        Iterator> iter = set.iterator();

        while (iter.hasNext()) {
            System.out.println(iter.next());

        }

        Map map = new HashMap();

        map.put(1, new Person(12, "anton"));
        map.put(2, new Person(42, "valera"));
        map.put(3, new Person(41, "vova"));

        Iterator iter1 = map.entrySet().iterator();

        while (iter1.hasNext()) {
            System.out.println(iter1.next());
        }

    }
}

    

Ответы

Ответ 1

Это принципиально разные структуры данных и используются они для разных целей.

Set - это множество, то самое математическое множество. И соответственно использовать
его надо как множество, т.е. хранить набор уникальных элементов.

Map - это ассоциированный массив, который хранит пары ключ-значение, где ключ должен
быть уникальным, а значение нет.

Соответственно выбор правильной структуры надо делать на основе того какие действия
над этими данными вы собираетесь делать. Если только хранить набор уникальных значений
и проверять, что такое значение уже есть в структуре данных, то это Set. Если вам необходимо
периодически искать значение по ключу(например по ИД), то это Map.

Если же вам надо хранить просто список объектов и периодически проходить по всем
элементам этого списка(как в ваших примерах), то надо использовать List.

Относительно вопроса о временах операций, есть такие замечательные ссылки, где все
хорошо описано 

для Java: https://github.com/benblack86/java-snippets/blob/master/resources/java_collections.pdf

для Абстракций: http://bigocheatsheet.com/

Все они приведены в терминах Big-O нотаций, что это в принципе такое, можно почитать тут.


Ответ 2

Обход всех элементов Map — не самая нужная операция. Самая популярная и важная —
быстро получить значение по ключу. Для такого сценария ваш Set не годится: вы не можете
это сделать эффективно (не перебирая все ключи). Поэтому Map нужен.

Уместнее обратный вопрос: зачем HashSet, если его можно реализовать, например,
через HashMap и получить действительно все операции? По факту HashSet примерно
так и реализован (он внутри хранит HashMap). Существует он отдельным классом по большей
части для удобства.

Также замечу, что ваш Item реализован неправильно: даже в вашем сценарии вы не исключаете
одинаковый элементов в Set (у вас используется Object.equals и Object.hashCode по умолчанию,
соответственно элементы сравниваются по reference equality).

Можно ли узнать пересечение N множеств по частям <N?

#множества #алгоритм

Есть списки уникальных целых значений. Каждый список назову «множеством».
Есть возможность узнавать кол-во уникальных элементов для максимум M множеств. Например:
/* допустим, мн-ва A и B такие, на деле состав множеств неизвестен */
A = [1,2,3]
B = [2,3,4,5]
/* можем задавать такие запросы и получать такие результаты: */
unique(A,B) = 5  /* 1,2,3,4,5 */
unique(A) = 3
unique(B) = 4

Хочется узнать кол-во общих элементов для N множеств, где N > M. Возможно ли это
в заданных условиях?
Запросов про unique() можно делать много. Как отсюда можно прийти к числу общих,
для 2, понятно:
unique(A) + unique(B) - unique(A,B) = общее ядро A и B

3 + 4 - 5 = 2 в примере выше.
Не соображу, как поступать с бОльшим числом множеств. К сожалению, прогулял теорию
множеств в своё время, поэтому прошу помощь у зала.    

Ответы

Ответ 1

Задача в общем случае нерешаема.
Пример: пусть M = 1, N = 2, все множества одноэлементные. Вы никак не сможете узнать,
эти множества совпадают или нет.

Флаги, или аналог множества в C#, как лучше реализовать?

#c_sharp #множества

Есть некий метод, пусть public static bool IsNewFileActual(sting oldFile, string
newFile, ComparsionFlags flags) сравнивающий 2 файла по набору критериев. Сами критерии,
для наглядности, например, такие: сравнение по дате последней записи в файл, версия
файла, MD5-хэш, размер файла.

В зависимости от некоторых условий, должна формироваться переменная flags, которая
будет задавать флаги для критериев проверки (например, флаг проверки по номеру версии
будет справедлив для *.EXE и *.DLL, а вот для *.PNG или *.HTML он не нужен).

В паскале (Delphi), я бы работал примерно так:

type 
   TComparsionFlags = set of (cfDate, cfVersion, cfHash, cfSize);
var
  CF : TComparsionFlags;
...
CF := [];
CF := CF + [cfVersion]; 
...
СF := CF + [cfHash, cfSize];
...
CF := CF - [cfDate];
...
if (cfDate in CF) then 
  begin
  ...
  end;


Иными словами, описал бы множество с возможными флагами, и использовал бы средства
языка для достижения своих целей.

Насколько я знаю, аналога паскалевских множеств в C# в чистом виде нет, и в качестве
замены можно использовать enum, что я и делаю:

[Flags]
public enum ComparsionFlags : byte
{
    cfVersion = 1,
    cfSize = 2,
    cfDate = 4,
    cfHash = 8,
}


После чего перед вызовом метода IsNewFileActual объявляю переменную ComparsionFlags
flags и далее задаю флаги так:

flags = ComparsionFlags.cfSize | ComparsionFlags.cfDate | ComparsionFlags.cfHash;


Как по мне, так это не очень удобно (по меньшей мере, как минимум, не лаконично),
как для задания самой переменной flags, так и для проверок значений, которые переданы
в этой переменной внутрь метода.

Собственно, вопрос и в заголовке, и вот, более детально:

Как наилучшим образом реализовать тип ComparsionFlags для использования переменных
данного типа в качестве набора флагов?

Может быть есть альтернативные, более удобные способы выполнить описанную задачу? 

Буду признателен за внимание и дельные советы/ответы. Спасибо.

P.S. Думал про List и HashTable, но есть ощущение, что это несколько не то...
Например, ничто не мешает добавить в List какой-то флаг n раз, и при удалении этого
флага из списка придется просматривать его весь, и удалять все вхождения этого флага
(или флагов), т.е. получаем, что нужно довольно много обвязки вокруг списка делать.
    

Ответы

Ответ 1

Использование флагов выглядит достаточно лаконично. Если переписать код с Delphi,
получится примерно так:

ComparsionFlags CF = default(ComparsionFlags);

CF = CF | ComparsionFlags.cfVersion; 
...
СF = CF | ComparsionFlags.cfHash | ComparsionFlags.cfSize;
...
CF = CF & ~ComparsionFlags.cfDate;
...
if (CF.HasFlag(ComparsionFlags.cfDate)) { 
  ...
}


Если использовать using static, то имя enum можно опускать:

using static ComparsionFlags;
...

ComparsionFlags CF = default(ComparsionFlags);

CF |= cfVersion; 
...
СF |= cfHash | cfSize;
...
CF &= ~cfDate;
...
if (CF.HasFlag(cfDate)) { 
  ...
}


В противовес, можно использовать класс HashSet, как указано в соседнем ответе:

HashSet flags = new HashSet();

CF.Add(ComparsionFlags.cfVersion); 
...
СF.UnionWith(new[]{ComparsionFlags.cfHash,ComparsionFlags.cfSize});
...
CF.Remove(ComparsionFlags.cfDate);
...
if (CF.Contains(ComparsionFlags.cfDate)) { 
  ...
}


Как можно заметить, в этом случае не обязательно делать значения enum флагами, то
есть значения могут идти и подряд: 1,2,3..., а не 1,2,4...


Ответ 2

Я бы написал HashSet

Генерация пересекающихся подмножеств

#алгоритм #множества

Был вчера в гостях, где моему малому показали игру Доббль. В ней имеется набор карточек
с резными пиктограммами, го главное - на любых двух карточках всегда имеется одна и
только одна общая пиктограмма.

С математической точки зрения это означает - имеется множество из N элементов; нужно
построить как можно большее количество подмножеств из M < N элементов, обладающих тем
свойством, что каждые два подмножества имеют один и только один общий элемент.

Как решить эту задачу? Каким алгоритмом сгенерировать эти подмножества? Пусть хоть
для каких-то нетривиальных вариантов - для 3 и 2, как вы понимаете, решение тривиальное
:), как и решение с единственным для всех общим элементом.

Буду признателен как за готовое решение, так и за любые идеи. 
    

Ответы

Ответ 1

Ответ 1-ый - не верный, потому как недооценил всей прелести поставленной проблемы

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

Ответ 2-ой - к сожалению не мой, неудержался, подсмотрел на просторах инета. 

\#define PRINT(x) printf("%2d  ", (x)+1)

main() {
int i, j, k, r = 0, n = 7;

// first card
printf ("Card %2d:  ", ++r);
for (i = 0; i <= n; i++) {
    PRINT (i);
}
printf ("\n");

// n following cards
for (j = 0; j < n; j++) {
    printf ("Card %2d:  ", ++r);
    PRINT (0);
    for (k = 0; k < n; k++) {
        PRINT (n+1 + n*j + k);
    }
    printf ("\n");
}

// n*n following cards
for (i = 0; i < n; i++) {
    for (j = 0; j < n; j++) {
        printf ("Card %2d:  ", ++r);
        PRINT (i+1);
        for (k = 0; k < n; k++) {
            PRINT (n+1 + n*k + (i*k+j)%n); // Good for n = prime number
        }
        printf ("\n");
    }
  }
}


А здесь можно посмотреть решение в действии


Ответ 2

имеется множество из N элементов; нужно построить как можно большее количество подмножеств
из M < N элементов, обладающих тем свойством, что каждые два подмножества имеют один
и только один общий элемент.


Давайте думать. Что имеем? У нас есть N элементов. В каждой группе должно быть M
элементов. 

Создадим первую группу. Допустим, в неё включены элементы с номерами от 1 до M. 

Создадим вторую группу. Она должна иметь с первой только 1 общий элемент. Пусть это
будет элемент 1. Тогда вторая группа содержит элемент 1 и элементы от M+1 до 2*M-1.

Создадим третью группу. Она должна иметь с каждой из ранее созданных только по 1
общему элементу. Ну вариант, когда это опять элемент 1, отметём как тривиальный (но
не как невозможный!!!). Тогда это будут элементы 2 (пересекаемся с группой 1) и M+1
(пересекаемся с группой 2), а остальные - это элементы с номерами от 2*M до 3*M-3.

Надеюсь, методика понятна? ну а дальше - самостоятельно... пока не выскочите за N,
или пока не кончатся варианты.

PS. Чую запах совершенных чисел...


Ответ 3

Резервируем первый элемент из N.
Разбиваем оставшиеся элементы в группы по M-1 элементов.
Добавляем в каждую из групп зарезервированный элемент.


Ответ 4

Случайно увидел в голове перед сном такой вариант для случая N=M(M-1)/2. Причём число
подмножеств M, а их размер M-1.

Пронумеруем элементы исходного множества числами от 1 до N, а генерируемые множества
обозначим A1, A2, ..., AM.

Берём элемент 1 и кладём его в множества A1 и A2. Берём элемент 2 и кладём его в
множества A1 и A3, затем элемент 3 в A1 и A4 и так далее до A1 и AM. Затем как бы возвращаемся
к началу и кладём очередной элемент (с номером M) в множества A2 и A3, затем (элемент
M+1) в A2 и A4 и т. д. Пример для N=6 и M=4:

123
145
426
563


Пример для N=10 и M=5 (вместо 10 написал 0):

1234
1567
5289
6830
7904


Доказательство придумывать, к сожалению, некогда.

Как скомпрессировать набор натуральных чисел? Порядок неважен, повторов нет.

#множества #сжатие #алгоритм #сравнение #компрессия

Задача сравнить два набора уникальных целых положительных чисел, и найти присутствующие
сразу в обоих. Все точно лежат в диапазоне от 1 до 200 млн. Обычно в каждом из двух
наборов от 0 до 5 млн чисел.
До сих пор делаю "в лоб": оба сета заношу во временные таблицы MySQL. Две одноколоночные
таблицы, где числа – первичные ключи. Сравнение проходит быстро, если сеты маленькие
и помещаются в engine=MEMORY. Медленно, когда таблицы большие и приходится создавать
их на диске. Когда надо таких сравнений выполнять помногу и часто — тормоза.
Что, если воспроизвести индексированные колонки MySQL в собственном коде? Один из
сетов держать в памяти, а каждый элемент второго проверять на наличие в первом.
Не хранить каждое из чисел набора (32бит, 2.5млн в среднем = 80Мб), а работать с
битовой маской всех возможных значений. 200 млн это, с запасом, 2^28 = 268,435,456
бит = 32Мб. Установлен – число есть в наборе, 0 – нет. Сравнивать установленные биты. 
В полном виде хранить для каждого сета весь набор битов неэффективно. Наверняка,
можно такие данные здорово компрессировать. Большинство битов будут 0, значит, их последовательности
можно кодировать их кол-вом подряд например. 
Вопрос к такому компрессированному массиву будет один: есть ли очередное искомое
число в наборе, или нет?
Упростим для примера. Пусть всего может быть 32 значения: 0..31. Наш массив будет
состоять из 32 нулей/единиц. В наборе присутствуют всего два значения: 17 и 22. 16
нулей, единица, 4 нуля, 1. И запишем их как 16,4: 10000100. Всего 8 бит вместо 2*6.
компрессия сэкономила 25%. Но это моё совсем косолапое представление о возможном способе
компрессии, без разделителей, единиц подряд и т.п.
Надо узнать про число 19, есть ли в наборе? Проходим по нашим 8 битам: 16 ещё пока
меньше 19, ещё 4 — уже перебор, ответ "нет в наборе".
Как по-вашему, есть ли вообще смысл в таком велосипеде, может ли он ускорить сравнение
двух сетов, по сравнению с MySQL?
Upd. Проще сформулирую вопрос. Ищется компрессия для данных, когда известны их параметры
и ограничения: только натуральные числа от .. до .., не подряд, не сортированные, без
повторов, порядок неважен. И даже без необходимости распаковки: нужно лишь уметь ответить
на вопрос «есть ли такое-то число в наборе, или нет?».    

Ответы

Ответ 1

1) БД не для решения таких задач
2) используем либо упорядоченные списки, либо хештаблицы 
3) я бы использовал упорядоченный список или массив, и потом сравнивал методом попарного
слияния:
 - оба указателя на первые элементы

берем элемент с первого списка,
сравниваем с элементом второго списка
если значения равны, то элемен заносим в список результата и увеличиваем оба указателя
и к пп 1
если 1 < 2, увеличиваем значение указателя первого списка
иначе второго

итого, используемые алгоритмы: 2 * qsort и попарного слияния
если списки ну очень большие...(20 млн вполне терпимо для памяти, но 200 может быть
уже перебором), то их можно разбить на части и сравнивать сперва часть 1, потом часть 2.
Алгоритм приблизительно следующий: есть списки 1: А+Б+С+Д... и 2:А+Б+С+Д...
 - сравниваем список 1А и 2А

если список 1А закончился, то сравниваем конец списка 2А и список 1Б
иначе конец списка 2Б со списоком 1А
как только какой список заканчивается текущим становится следующий из данной последовательности
(1 или 2 )
и так далее


Ответ 2

Я бы начал с простых решений и замеров времени выполнения для разных наборов данных.
Вы можете всегда хранить данные в заранее подготовленном виде (Например уже в бинарном
дереве или в отсортированном массиве)? Тогда находить элементы можно примерно так:
    // для отсортированным массивов. Сложность О(a.length + b.length)
    public static List GetSameNumber(Int32[] a, Int32[] b) {
        var i = 0;
        var j = 0;
        var ans = new List();
        while (i < a.Length && j < b.Length) {
            if (a[i] == b[j]) {
                ans.Add(a[i]);
                i++;
                j++;
            } else if (a[i] > b[j])
                j++;
            else i++;

        }

        return ans;
    } 
    // для бинарных деревьев. Сложность О(a.length) или О(a.length + b.length)в зависимости
от реализации
    public static List GetSameNumber(SortedSet a, SortedSet b) {
        var ans = new List();
        foreach (var i in a) {
            if (b.Contains(i))
                ans.Add(i);
        }
        return ans;
        //var ansset = new SortedSet(a);
        //ansset.IntersectWith(b);
        //return ansset.ToList(); // или просто return ansset
    }

Если данные нельзя хранить в нужном виде, то переводить в него каждый раз при вызове.
Тут появляется О(nlogn) для создания бинарного дерева или сортировки массива.
Большое дерево с битами на 8Гб наверно даст пенальти по кешу и пейджингу.

Обращение к 2 соседним элементам std::set

#cpp #множества

Возникла задача, в которой надо обращаться с двумя соседними элементами множества
set. Такой вопрос: как это сделать? Гуглил, нигде не нашел информации по этому поводу,
уже сомневаюсь, что так вообще можно делать. Например, у вектора этот вопрос решается
так: v[i] - i-й элемент, а v[i+1] - соседний элемент. Можно ли делать что-то аналогичное
во множестве? Метод find() не предлагать, так как я не знаю, какие числа лежат в контейнерах.
    

Ответы

Ответ 1

Воспользуйтесь итераторами. Если итератор it указывает на нужный вам элемент set,
например, найденный с помощью find() или, скажем, первый элемент, полученный с помощью
begin(), то после выполнения ++it этот итератор будет указывать на следующий элемент
контейнера.

Подскажите функцию, похожую на хэш, но короче и без коллизий

#алгоритм #хеширование #множества

Требуется генерировать из последовательных целых, уникальные непоследовательные n-значные
коды. Представьте хэши, серийники, или номера купонов. Целочисленному id от 0 до K
соответствует строго один n-значный код. И важно, чтобы последовательно идущие коды
сильно различались, а не одним-двумя символами.

Пример:

0    KXBR6Z
1    8FLWGG
2    PAZT73


Из-за коллизий и краткости требуемых кодов, популярные хэш-функции не подходят. Криптостойкость
не требуется. Если злодеи разгадают алгоритм, пусть хоть все коды распечатают. Делается
для красоты. Хотя, рассмотреть, от чего зависит сложность отгадывания алгоритма по
X имеющимся на руках кодам тоже интересно!

Вопрос: подскажите алгоритм / функцию f(i) = s для соответствия между множествами
0..K и n-значными ABC123XYZ. Обратная функция была бы тоже интересна: f1(s) = i чтобы
из кода получить целое, либо узнать, что код невалиден. 

Наверняка, задача не нова, но не придумал, как искать ответ. Требуется human-трансляция. )

P.S. ищу именно "математику", алгоритм, а не способ забить в БД уникальные значения,
каждый раз при создании нового, проверяя уникальность.
    

Ответы

Ответ 1

С такой задачей хорошо справляются шифры подстановки. Первое, что Вам надо сделать
- это расширить алфавит (перейти от цифр к буквам, где несколько букв будут соответствовать
одной цифре). Если для Вас очень важно скрыть исходные значение, то имеет смысл предварительно
зашифровать данные блочным или асиметричным шифрованием.
накидал пример кода с подстановкой, результат:
input/encoded/decoded - 123 / efg / 123
input/encoded/decoded - 456 / hij / 456
input/encoded/decoded - 789 / abc / 789
input/encoded/decoded - 012 / def / 012
input/encoded/decoded - 1157232188 / eoiafgpybl / 1157232188

сам код:
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;

public class Substitution {
    private static final int NUMBER_COUNT = 10;
    private static final int LETTER_COUNT = 26;
    private static final int ZERO_ASCII_CODE = 48;
    private static final int A_CHAR_ASCII_CODE = 97;

    // substitution tables
    private static final Map> numToChar = new HashMap>(
            NUMBER_COUNT);
    private static final Map charToNum = new HashMap(
            LETTER_COUNT);

    // init tables
    static {
        // add list containers
        for (int i = 0; i < NUMBER_COUNT; i++) {
            numToChar.put(Character.valueOf((char) (ZERO_ASCII_CODE + i)),
                    new LinkedList());
        }

        // init substitution table
        for (int i = A_CHAR_ASCII_CODE; i < A_CHAR_ASCII_CODE + LETTER_COUNT; i++) {

            // number = (symbol ascii code) mod 9
            Character num = Character
                    .valueOf((char) (i % NUMBER_COUNT + ZERO_ASCII_CODE));
            Character ch = Character.valueOf((char) i);

            numToChar.get(num).add(ch);
            charToNum.put(ch, num);
        }
    }

    public static void main(String[] args) {
        System.out.println("dumping straight substitution table");
        for (Character num : numToChar.keySet()) {
            System.out.println("num to char - " + num + ", replacements = "
                    + numToChar.get(num));
        }
        System.out.println();
        System.out.println("dumping reverse substitution table");
        for (Character ch : charToNum.keySet()) {
            System.out.println("char to num - " + ch + ", replacements = "
                    + charToNum.get(ch));
        }

        // test
        String[] nums = new String[] { "123", "456", "789", "012", "1157232188" };
        String r = null;
        for (int i = 0; i < nums.length; i++) {
            r = decode(nums[i], true);
            System.out.println("input/encoded/decoded - " + nums[i] + " / " + r
                    + " / " + decode(r, false));
        }

    }

    public static String decode(String input, boolean direction) {
        // result buffer
        StringBuilder b = new StringBuilder(input.length());

        // ensure all latters are in lower case
        String data = input.toLowerCase();

        // store indexes (determines which letter to use when coding a number)
        Map indexes = new HashMap();

        // encode string
        for (int i = 0; i < input.length(); i++) {
            b.append(decode(indexes, data.charAt(i), direction));
        }

        return b.toString();
    }

    // straight - number to letter
    // reverse - letter to number
    private static Character decode(Map indexes, char ch,
            boolean direction) {
        // convert character
        Character character = Character.valueOf(ch);
        if (direction) {
            // get list
            List list = numToChar.get(character);

            // get index to use
            Integer index = indexes.get(character);
            if (null == index) {
                index = Integer.valueOf(0);
            }

            // update index map
            int next = index.intValue() + 1;
            if (next == list.size()) {
                next = 0;
            }

            indexes.put(character, Integer.valueOf(next));

            return list.get(index);
        }

        return charToNum.get(character);
    }
}

Данный пример строго "заточен" под цифры и буквы, но, по аналогии, можно сделать
код который будет делать подстановки отдельных символов и/или их последовательностей


Ответ 2

В качестве одного из плохих вариантов, который, тем не менее, решает задачу, могу
предложить следующий подход (плох он из соображений, описанных ниже): 



  
  Кодировать исходный номер купона N в системе кодирования Base36.
  Дописывать недостающие нули в начало для того, чтобы получить желаемую длину кода.
  Совершать какие-либо битовые преобразования, чтобы коды для N и N + 1 не выглядели
похожими, сохраняющие биективность и эффективную вычислимость обратной функции.
  



Сама по себе постановка задачи немного странная - требуется найти биективную функцию,
для которой существует эффективно вычислимая обратная функция ("чтобы из кода получить
целое"). В такой постановка любой купон или серийник, выданный пользователю, автоматически
уязвим для для реверсинга.



  Если выгода, получаемая с такого купона / серийника / ... окажется достаточной,
то наверняка найдется человек, который найдет обратную функцию, а следовательно, сможет
проэксплуатировать систему.



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



  Нужно опять каким-то образом сравнивать хэши кодов купонов, исключать коллизии
и т.п. Мне кажется, что для кодов типа KXBR6Z можно доказать, что с приемлемой с практической
точки зрения вероятностью этого не получится. Хотя, возможно, здесь я упускаю что-то
очевидное. [?]



Вообще говоря, правильный подход к задаче такого рода (генерация уникального набора
купонов в БД и операции над этой БД) обладает целым набором преимуществ по сравнению
с решением, где используется некоторая предопределенная функция.



  Попробуйте представить, например, как проставить купону, полученному с помощью
некоторой функции, статус revoked или invalid. Или, скажем, разрешить использовать
какой-либо купон дважды.



Из референсов, которые могут быть полезны:



  
  Create a set of “coupon codes” based on an algorithm (см. про Partial Key Verification).
  [CPAN] CouponCode.


Ответ 3

У нас две задачи: сгенерировать для каждого купона уникальное число. Это называется
perfect hash. Вторая задача - сделать так, чтобы каждому купону соответствовало число
от 0 до N-1. Как решить обе эти задачи одним алгоритмом, я не представляю, но по отдельности
- вполне.
Код купона состоит из 6 символов, каждый из которых может иметь одно из 36 значений.
То есть код представляет собой шестизначное число в 36-ричной системе счисления! К
счастью, такое число укладывается в 32 бита. Можешь проверить по калькулятору, что
36^6 < 2^32.
unsigned to_hash(const char* coupon)
{
    unsigned hash = 0;
    char c;
    for( int i = 0; i < 6; ++i ) {
        c = coupon[i];
        if( c < 'A' ) {
            c -= '0';
        } else {
            c -= '7';
        }
        hash *= 36;
        hash += c;
    }
    return hash;
}

Теперь вторая задача - нумерация этих хэшей и поиск номера хэша по самому хэшу. Это
очень просто, если заранее составить массив хэшей купонов в возрастающем порядке и
определять индекс бинарным поиском. Если индекс не найден - значит, купон некорректный.
Если заранее составить массив хэшей невозможно, то задача усложняется, но ненамного.
Надо будет использовать индексированный список и сортировку вставками. Но это уже другая
история.


Ответ 4

Без коллизий нельзя (если хеш постоянной длины), на общем наборе данных. Для последовательности
чисел, чем md5 с солью и выделение части хеша необходимой длинны не подходит?
upd:
Если алгоритм на серверной стороне, возьми простое: серию, если таковая есть, и свою
уникальную соль. Проверку-то, снова будешь на сервере выполнять, в чем тогда отличие
от функции. Пример:
Серия: 101010
Код: e25019

Для них на сервере:
Серия:101010
Соль(приватные данные): Yap!
Md5(101010Yap!) = e2501912913cd181d4199bcea5dd401c
Выделил 6 символов. Проверил. И ты не зависишь от коллизий.

Единственный минус - утечет соль, или будет слишком маленькая по длине(возможность
перебора) - считай, что придется менять алгоритм (менять соль/править настройки безопасности
и т.п.).

Генерация формы множественного числа

#php #массивы #числа #множества #nlp

Здравствуй, дали задачу по PHP

Напишите массив с числами от 1 до 30
[1, 2, 3 ....]
и функцию, которая делает следующее
проходит по массиву и каждому числу дописывает фразу  "новых комментариев" и эти
слова склоняются в соответствии с их числом
и делает в итоге массив
1 новый комментарий
2 новых комментария
и тд
и вывести на экран в 
html в элементе 

Прошу помочь с примерами решения, в PHP я новичок, теорию изучил не плохо но сижу
несколько дней и не дошло пока что использовать в этом примере.
    

Ответы

Ответ 1

Есть статья относительно множественных чисел. Там собраны алгоримы определения множественного
числа для многих стран. Алгоритмы представлены в виде формул. Не нужно изобретать велосипед.
Мы же используем формулы в математике.

В данном случае мы берем русский язык: nplurals=3
То есть для русского языка три множественные формы: 
1) Когда элемент один. Например: 1 новый комментарий 
2) Когда элементов больше двух, но меньше пяти. Например: 3 комментария, 4 комментария
3) Когда элементов больше или равно пяти. Например: 5 новых комментариев, 6 новых
комменариев

Теперь перейдем к реализации. Условия привел в более читаемый вид:
    

$numbers = ['1', '2', '3', '4', '5'];

function plural($number)
{
    if ($number % 10 == 1 && $number % 100 != 11) {
        return $number . ' новый комментарий';
    } else {
        if ($number % 10 >= 2 && $number % 10 <= 4 && ($number % 100 < 10 || $number
% 100 >= 20)) {
            return ($number . ' новых комментария');
        } else {
            return ($number . ' новых комментариев');
        }
    }
}

foreach ($numbers as $number) {
    echo plural($number);
    echo '
';
}


Ответ 2

На мой взгляд самое элегантное решение функции plural такое:

function plural($number, $array){
   $keys = [2, 0, 1, 1, 1, 2];
   return $array[$number % 100 > 4 && $number % 100 < 20 ? 2 : $keys[min($number
% 10, 5)]];
}


Как это работает:  

Есть массив со склонениями 

$array[' новый комментарий', ' новых комментария', ' новых комментариев']


Cоставляем массив ключей  $keys = [2, 0, 1, 1, 1, 2];


$keys[0] = 2; → $array[2] = 'новых комментариев' → 0, 20, 30, 10020... 'новых комментариев'  
$keys[1] = 0; → $array[0] = 'новый комментарий' → 1, 21, 31... 'новый комментарий'  
$keys[2] = $keys[3] = $keys[4] = 1; → $array[1] = 'новых комментария' → 2, 3, 4,
31, 32, 33, 34 ... 'новых комментария'
$keys[5] = 2; → после 5-х всегда 'новых комментариев' → 5 'новых комментариев', 1006
'новых комментариев' 


Поэтому $array[$keys[min($number%10, 5)]]; 

На этом бы можно было закончить, НО...есть 11, 12, 13 'новый комментарий' — это исключение.
Запишем $number % 100 > 4 && $number % 100 < 20 ? 2

Итак, разобрались  с выражением $number%100 > 4 && $number%100 < 20 ? 2: что если
остаток отделения в пределах 4–20, то всегда - новых комментариев. 

Теперь составляем массив с элементами массива, а потом просто в цикле обходим весь
массив и конкатенируем его значение.

$arrays = [1,2,3,4,5,6,7,8,9,10];

foreach($arrays as $key=>$val) {
   $arrays[$key] .= plural($val, array(' новый комментарий', ' новых комментария',
' новых комментариев'));
}

var_dump($arrays);


Обновлено

Почему такой порядок ключей? $keys = [2, 0, 1, 1, 1, 2];   

Есть массив ключей $keys = [2, 0, 1, 1, 1, 2]; и массив склонений $array[' новый
комментарий', ' новых комментария', ' новых комментариев'].
Для простоты  рассмотрим значения от 0- 10:

0 - $keys[0] = 2, а $array[2] = "..ев";
1 - $keys[1] = 0, а $array[0]  = "..й";
2 - $keys[2] = 1, а $array[1]  = "..я";
3 - $keys[3] = 1, а $array[1] = "..я";
4 - $keys[4] = 1, а $array[1] = "..я";   

а всё что после пяти это будет "...ев"; 

5,6,7,8,9 - $keys[5] = 2 $array[2] "..ев";
По такому принципу можно склоняются все числа кроме 11,12,13,14

Зачем и в каких конкретно случаях нужно использовать HashMap, если мы можем сделать тоже самое используя HashSet?

Есть простой класс:
public class Person { private int age; private String name;
public Person(int age, String name) { this.age = age; this.name = name; }
public int getAge() { return age; }
public void setAge(int age) { this.age = age; }
public String getName() { return name; }
public void setName(String name) { this.name = name; }
@Override public String toString() { return "Person [age=" + age + ", name=" + name + "]"; }
}
Есть еще один класс:
public class Item { private K key; private P person; public Item(K key, P person) { this.key = key; this.person = person; } public K getKey() { return key; } public void setKey(K key) { this.key = key; } public P getPerson() { return person; } public void setPerson(P person) { this.person = person; } @Override public String toString() { return "Item [key=" + key + ", person=" + person + "]"; }
}
ГДЕ ПРАВДА???
И сама реализация классов:
public class Main { public static void main(String[] args) {
Set> set = new HashSet>();
set.add(new Item(1, new Person(23, "gogo"))); set.add(new Item(2, new Person(42, "niko"))); set.add(new Item(3, new Person(32, "toto")));
Iterator> iter = set.iterator();
while (iter.hasNext()) { System.out.println(iter.next());
}
Map map = new HashMap();
map.put(1, new Person(12, "anton")); map.put(2, new Person(42, "valera")); map.put(3, new Person(41, "vova"));
Iterator iter1 = map.entrySet().iterator();
while (iter1.hasNext()) { System.out.println(iter1.next()); }
} }

Ответ

Это принципиально разные структуры данных и используются они для разных целей.
Set - это множество, то самое математическое множество. И соответственно использовать его надо как множество, т.е. хранить набор уникальных элементов.
Map - это ассоциированный массив, который хранит пары ключ-значение, где ключ должен быть уникальным, а значение нет.
Соответственно выбор правильной структуры надо делать на основе того какие действия над этими данными вы собираетесь делать. Если только хранить набор уникальных значений и проверять, что такое значение уже есть в структуре данных, то это Set. Если вам необходимо периодически искать значение по ключу(например по ИД), то это Map
Если же вам надо хранить просто список объектов и периодически проходить по всем элементам этого списка(как в ваших примерах), то надо использовать List
Относительно вопроса о временах операций, есть такие замечательные ссылки, где все хорошо описано
для Java: https://github.com/benblack86/java-snippets/blob/master/resources/java_collections.pdf
для Абстракций: http://bigocheatsheet.com/
Все они приведены в терминах Big-O нотаций, что это в принципе такое, можно почитать тут

Флаги, или аналог множества в C#, как лучше реализовать?

Есть некий метод, пусть public static bool IsNewFileActual(sting oldFile, string newFile, ComparsionFlags flags) сравнивающий 2 файла по набору критериев. Сами критерии, для наглядности, например, такие: сравнение по дате последней записи в файл, версия файла, MD5-хэш, размер файла.
В зависимости от некоторых условий, должна формироваться переменная flags, которая будет задавать флаги для критериев проверки (например, флаг проверки по номеру версии будет справедлив для *.EXE и *.DLL, а вот для *.PNG или *.HTML он не нужен).
В паскале (Delphi), я бы работал примерно так:
type TComparsionFlags = set of (cfDate, cfVersion, cfHash, cfSize); var CF : TComparsionFlags; ... CF := []; CF := CF + [cfVersion]; ... СF := CF + [cfHash, cfSize]; ... CF := CF - [cfDate]; ... if (cfDate in CF) then begin ... end;
Иными словами, описал бы множество с возможными флагами, и использовал бы средства языка для достижения своих целей.
Насколько я знаю, аналога паскалевских множеств в C# в чистом виде нет, и в качестве замены можно использовать enum, что я и делаю:
[Flags] public enum ComparsionFlags : byte { cfVersion = 1, cfSize = 2, cfDate = 4, cfHash = 8, }
После чего перед вызовом метода IsNewFileActual объявляю переменную ComparsionFlags flags и далее задаю флаги так:
flags = ComparsionFlags.cfSize | ComparsionFlags.cfDate | ComparsionFlags.cfHash;
Как по мне, так это не очень удобно (по меньшей мере, как минимум, не лаконично), как для задания самой переменной flags, так и для проверок значений, которые переданы в этой переменной внутрь метода.
Собственно, вопрос и в заголовке, и вот, более детально:
Как наилучшим образом реализовать тип ComparsionFlags для использования переменных данного типа в качестве набора флагов?
Может быть есть альтернативные, более удобные способы выполнить описанную задачу?
Буду признателен за внимание и дельные советы/ответы. Спасибо.
P.S. Думал про List и HashTable, но есть ощущение, что это несколько не то... Например, ничто не мешает добавить в List какой-то флаг n раз, и при удалении этого флага из списка придется просматривать его весь, и удалять все вхождения этого флага (или флагов), т.е. получаем, что нужно довольно много обвязки вокруг списка делать.

Ответ

Использование флагов выглядит достаточно лаконично. Если переписать код с Delphi, получится примерно так:
ComparsionFlags CF = default(ComparsionFlags);
CF = CF | ComparsionFlags.cfVersion; ... СF = CF | ComparsionFlags.cfHash | ComparsionFlags.cfSize; ... CF = CF & ~ComparsionFlags.cfDate; ... if (CF.HasFlag(ComparsionFlags.cfDate)) { ... }
Если использовать using static, то имя enum можно опускать:
using static ComparsionFlags; ...
ComparsionFlags CF = default(ComparsionFlags);
CF |= cfVersion; ... СF |= cfHash | cfSize; ... CF &= ~cfDate; ... if (CF.HasFlag(cfDate)) { ... }
В противовес, можно использовать класс HashSet, как указано в соседнем ответе:
HashSet flags = new HashSet();
CF.Add(ComparsionFlags.cfVersion); ... СF.UnionWith(new[]{ComparsionFlags.cfHash,ComparsionFlags.cfSize}); ... CF.Remove(ComparsionFlags.cfDate); ... if (CF.Contains(ComparsionFlags.cfDate)) { ... }
Как можно заметить, в этом случае не обязательно делать значения enum флагами, то есть значения могут идти и подряд: 1,2,3..., а не 1,2,4...

Генерация формы множественного числа

Здравствуй, дали задачу по PHP
Напишите массив с числами от 1 до 30 [1, 2, 3 ....] и функцию, которая делает следующее проходит по массиву и каждому числу дописывает фразу "новых комментариев" и эти слова склоняются в соответствии с их числом и делает в итоге массив 1 новый комментарий 2 новых комментария и тд и вывести на экран в html в элементе
Прошу помочь с примерами решения, в PHP я новичок, теорию изучил не плохо но сижу несколько дней и не дошло пока что использовать в этом примере.

Ответ

Есть статья относительно множественных чисел. Там собраны алгоримы определения множественного числа для многих стран. Алгоритмы представлены в виде формул. Не нужно изобретать велосипед. Мы же используем формулы в математике.
В данном случае мы берем русский язык: nplurals=3 То есть для русского языка три множественные формы: 1) Когда элемент один. Например: 1 новый комментарий 2) Когда элементов больше двух, но меньше пяти. Например: 3 комментария, 4 комментария 3) Когда элементов больше или равно пяти. Например: 5 новых комментариев, 6 новых комменариев
Теперь перейдем к реализации. Условия привел в более читаемый вид:
$numbers = ['1', '2', '3', '4', '5'];
function plural($number) { if ($number % 10 == 1 && $number % 100 != 11) { return $number . ' новый комментарий'; } else { if ($number % 10 >= 2 && $number % 10 <= 4 && ($number % 100 < 10 || $number % 100 >= 20)) { return ($number . ' новых комментария'); } else { return ($number . ' новых комментариев'); } } }
foreach ($numbers as $number) { echo plural($number); echo '
'; }

Как скомпрессировать набор натуральных чисел? Порядок неважен, повторов нет.

Задача сравнить два набора уникальных целых положительных чисел, и найти присутствующие сразу в обоих. Все точно лежат в диапазоне от 1 до 200 млн. Обычно в каждом из двух наборов от 0 до 5 млн чисел. До сих пор делаю "в лоб": оба сета заношу во временные таблицы MySQL. Две одноколоночные таблицы, где числа – первичные ключи. Сравнение проходит быстро, если сеты маленькие и помещаются в engine=MEMORY. Медленно, когда таблицы большие и приходится создавать их на диске. Когда надо таких сравнений выполнять помногу и часто — тормоза. Что, если воспроизвести индексированные колонки MySQL в собственном коде? Один из сетов держать в памяти, а каждый элемент второго проверять на наличие в первом. Не хранить каждое из чисел набора (32бит, 2.5млн в среднем = 80Мб), а работать с битовой маской всех возможных значений. 200 млн это, с запасом, 2^28 = 268,435,456 бит = 32Мб. Установлен – число есть в наборе, 0 – нет. Сравнивать установленные биты. В полном виде хранить для каждого сета весь набор битов неэффективно. Наверняка, можно такие данные здорово компрессировать. Большинство битов будут 0, значит, их последовательности можно кодировать их кол-вом подряд например. Вопрос к такому компрессированному массиву будет один: есть ли очередное искомое число в наборе, или нет? Упростим для примера. Пусть всего может быть 32 значения: 0..31. Наш массив будет состоять из 32 нулей/единиц. В наборе присутствуют всего два значения: 17 и 22. 16 нулей, единица, 4 нуля, 1. И запишем их как 16,4: 10000100. Всего 8 бит вместо 2*6. компрессия сэкономила 25%. Но это моё совсем косолапое представление о возможном способе компрессии, без разделителей, единиц подряд и т.п. Надо узнать про число 19, есть ли в наборе? Проходим по нашим 8 битам: 16 ещё пока меньше 19, ещё 4 — уже перебор, ответ "нет в наборе". Как по-вашему, есть ли вообще смысл в таком велосипеде, может ли он ускорить сравнение двух сетов, по сравнению с MySQL? Upd. Проще сформулирую вопрос. Ищется компрессия для данных, когда известны их параметры и ограничения: только натуральные числа от .. до .., не подряд, не сортированные, без повторов, порядок неважен. И даже без необходимости распаковки: нужно лишь уметь ответить на вопрос «есть ли такое-то число в наборе, или нет?».

Ответ

1) БД не для решения таких задач 2) используем либо упорядоченные списки, либо хештаблицы 3) я бы использовал упорядоченный список или массив, и потом сравнивал методом попарного слияния: - оба указателя на первые элементы берем элемент с первого списка, сравниваем с элементом второго списка если значения равны, то элемен заносим в список результата и увеличиваем оба указателя и к пп 1 если 1 < 2, увеличиваем значение указателя первого списка иначе второго итого, используемые алгоритмы: 2 * qsort и попарного слияния если списки ну очень большие...(20 млн вполне терпимо для памяти, но 200 может быть уже перебором), то их можно разбить на части и сравнивать сперва часть 1, потом часть 2. Алгоритм приблизительно следующий: есть списки 1: А+Б+С+Д... и 2:А+Б+С+Д... - сравниваем список 1А и 2А если список 1А закончился, то сравниваем конец списка 2А и список 1Б иначе конец списка 2Б со списоком 1А как только какой список заканчивается текущим становится следующий из данной последовательности (1 или 2 ) и так далее

Подскажите функцию, похожую на хэш, но короче и без коллизий

Требуется генерировать из последовательных целых, уникальные непоследовательные n-значные коды. Представьте хэши, серийники, или номера купонов. Целочисленному id от 0 до K соответствует строго один n-значный код. И важно, чтобы последовательно идущие коды сильно различались, а не одним-двумя символами.
Пример:
0 KXBR6Z 1 8FLWGG 2 PAZT73
Из-за коллизий и краткости требуемых кодов, популярные хэш-функции не подходят. Криптостойкость не требуется. Если злодеи разгадают алгоритм, пусть хоть все коды распечатают. Делается для красоты. Хотя, рассмотреть, от чего зависит сложность отгадывания алгоритма по X имеющимся на руках кодам тоже интересно!
Вопрос: подскажите алгоритм / функцию f(i) = s для соответствия между множествами 0..K и n-значными ABC123XYZ. Обратная функция была бы тоже интересна: f1(s) = i чтобы из кода получить целое, либо узнать, что код невалиден.
Наверняка, задача не нова, но не придумал, как искать ответ. Требуется human-трансляция. )
P.S. ищу именно "математику", алгоритм, а не способ забить в БД уникальные значения, каждый раз при создании нового, проверяя уникальность.

Ответ

С такой задачей хорошо справляются шифры подстановки. Первое, что Вам надо сделать - это расширить алфавит (перейти от цифр к буквам, где несколько букв будут соответствовать одной цифре). Если для Вас очень важно скрыть исходные значение, то имеет смысл предварительно зашифровать данные блочным или асиметричным шифрованием. накидал пример кода с подстановкой, результат: input/encoded/decoded - 123 / efg / 123 input/encoded/decoded - 456 / hij / 456 input/encoded/decoded - 789 / abc / 789 input/encoded/decoded - 012 / def / 012 input/encoded/decoded - 1157232188 / eoiafgpybl / 1157232188 сам код: import java.util.HashMap; import java.util.LinkedList; import java.util.List; import java.util.Map;
public class Substitution { private static final int NUMBER_COUNT = 10; private static final int LETTER_COUNT = 26; private static final int ZERO_ASCII_CODE = 48; private static final int A_CHAR_ASCII_CODE = 97;
// substitution tables private static final Map> numToChar = new HashMap>( NUMBER_COUNT); private static final Map charToNum = new HashMap( LETTER_COUNT);
// init tables static { // add list containers for (int i = 0; i < NUMBER_COUNT; i++) { numToChar.put(Character.valueOf((char) (ZERO_ASCII_CODE + i)), new LinkedList()); }
// init substitution table for (int i = A_CHAR_ASCII_CODE; i < A_CHAR_ASCII_CODE + LETTER_COUNT; i++) {
// number = (symbol ascii code) mod 9 Character num = Character .valueOf((char) (i % NUMBER_COUNT + ZERO_ASCII_CODE)); Character ch = Character.valueOf((char) i);
numToChar.get(num).add(ch); charToNum.put(ch, num); } }
public static void main(String[] args) { System.out.println("dumping straight substitution table"); for (Character num : numToChar.keySet()) { System.out.println("num to char - " + num + ", replacements = " + numToChar.get(num)); } System.out.println(); System.out.println("dumping reverse substitution table"); for (Character ch : charToNum.keySet()) { System.out.println("char to num - " + ch + ", replacements = " + charToNum.get(ch)); }
// test String[] nums = new String[] { "123", "456", "789", "012", "1157232188" }; String r = null; for (int i = 0; i < nums.length; i++) { r = decode(nums[i], true); System.out.println("input/encoded/decoded - " + nums[i] + " / " + r + " / " + decode(r, false)); }
}
public static String decode(String input, boolean direction) { // result buffer StringBuilder b = new StringBuilder(input.length());
// ensure all latters are in lower case String data = input.toLowerCase();
// store indexes (determines which letter to use when coding a number) Map indexes = new HashMap();
// encode string for (int i = 0; i < input.length(); i++) { b.append(decode(indexes, data.charAt(i), direction)); }
return b.toString(); }
// straight - number to letter // reverse - letter to number private static Character decode(Map indexes, char ch, boolean direction) { // convert character Character character = Character.valueOf(ch); if (direction) { // get list List list = numToChar.get(character);
// get index to use Integer index = indexes.get(character); if (null == index) { index = Integer.valueOf(0); }
// update index map int next = index.intValue() + 1; if (next == list.size()) { next = 0; }
indexes.put(character, Integer.valueOf(next));
return list.get(index); }
return charToNum.get(character); } } Данный пример строго "заточен" под цифры и буквы, но, по аналогии, можно сделать код который будет делать подстановки отдельных символов и/или их последовательностей