0

Given an array like ['8', '2', '5', '3'], and an integer n. Write a function to generate id, the id can not contain n continuous digit. All the digit must from the given array.

For example, if n equals to 2, the current id is 8253, the next will be 8258, because 8255 has two 5 continuously.

How to solve it？

He Yuntao
  • 86
  • 11
  • If `current id` is `8253` for `n=2`, then why `next id` is `8258` and not `8254`? – Raj Dec 09 '19 at 05:31
  • because the digit of id from the given array. given array is [8, 2, 5, 3], not contain 4 – He Yuntao Dec 09 '19 at 06:01
  • Use `next_permutation` and check if it contains n continuous digits. https://stackoverflow.com/questions/11483060/stdnext-permutation-implementation-explanation – Raj Dec 09 '19 at 06:04
  • @Raj Thanks a lot. That is helpful for me. But in my case, the element in array is allowed repeatedly, and the length of id is infinitely. So, it may be 8325825832, '''next_permutation''' can not solve this problem – He Yuntao Dec 09 '19 at 06:48
  • you can implement `rank` (get index of a given permutation) and `unrank` (create a permutation from given index) methods; https://stackoverflow.com/questions/31702845/permutations-unrank – Dmitry Bychenko Dec 09 '19 at 07:33

1 Answers1

2

I suggest to use N-base integer system. So for above example, we can use 5-base system.

  1. First sort the array of digits - that is ['2', '3', '5', '8'], and each digit will match new base number started from 1. For example, '2'->1, '3'->2, '5'->3, '8'->4 I assigned from 1 not 0, because '235' and '2235' will be same '012' and '0012' if we start from 0.

  2. For number "8253" we can change to base "4132"

  3. and we add one by one from "4132" (5-base integer system) and check if it contains 0 or consecutive n same digits.

Hope this could help, though a little complicated.

Pro Magic
  • 76
  • 1
  • 5