1. Выбирать число от 1 до n
2. Если оно уникальное и размер выборки меньше k, то сохранять в выборку, иначе пропустить
3. Повторить шаг 1
Вот так написал, выглядит честно. Хотя бы за счет того, что шаг 1 одинаков. Склоняюсь взять готовую реализацию, приняв на веру, что она правильная. А то много времени уже ушло ))