c++ - List of 10 digit strings where every 4 digit substring is unique -



c++ - List of 10 digit strings where every 4 digit substring is unique -

in past competition, asked generate 10 digit strings using digits 0 9 1 time each. four-digit substring used in string cannot used again.

what highest number of unique strings can generate using these rules? list them.

example:

if utilize string 0243697518 in list, can not generate strings contain 0243, 2436, 4369, 3697, 6975, 9751 , 7518

to solve problem, have written c++ program, scans permutation of "0123456789" , add together them solution list if 4 digit sub-strings of code has not been used before. problem of algorithm size of solution list varies depending on starting point add together list first. if start adding list "0123456789", list ends 504 entries not maximum asked. wonder how solve question, help highly appreciated. i'm open hear mathematical solution or algorithm suggestions generate list asked.

#include <iostream> #include <cstdint> #include <vector> #include <set> #include <algorithm> using namespace std; void main(void) { set<string> substring_list; // holds list of used 4 digit sub-strings set<string> solution_list; string code = "0123456789"; { vector<string> subs; (int = 0; < 7; i++) { // adds 4 digits sub-strings used in code subs.push_back(code.substr(i, 4)); } if ((substring_list.find(subs[0]) == substring_list.end()) && (substring_list.find(subs[1]) == substring_list.end()) && (substring_list.find(subs[2]) == substring_list.end()) && (substring_list.find(subs[3]) == substring_list.end()) && (substring_list.find(subs[4]) == substring_list.end()) && (substring_list.find(subs[5]) == substring_list.end()) && (substring_list.find(subs[6]) == substring_list.end())) { // if substrings unique , not used before // add together code solution list solution_list.insert(code); // add together newly added code's substrings substring list. (auto s: subs) { substring_list.insert(s); } } } while (next_permutation(code.begin(), code.end())); cout << solution_list.size() << endl; }

c++ algorithm math graph-theory

Comments

Post a Comment

Popular posts from this blog

Delphi change the assembly code of a running process -

Delphi change the assembly code of a running process - i'm trying alter address 00741fa5 has push test.009e721c . alter push test.009e71c8 . procedure callback; asm force $9e71c8 end; procedure tform2.btn1click(sender: tobject); var ppid :dword; pprocess : cardinal; begin getwindowthreadprocessid(findwindow(nil,pchar('test')), @ppid); pprocess := openprocess(process_all_access, false, ppid); injectasm(pprocess, $741fa5, 10, integer(@callback), 0); end; here injectasm function (with error checking) function injectasm(process: longword; injectaddress, injectsize, codeaddress, codesize : integer): pointer; var csize, rsize : integer; replaced : array of byte; jmp : array [0..4] of byte; jmpaddress : integer; nopv : byte; : integer; nbr: ulong_ptr; begin //injectsize must equal or greater 5, because need space our //(far) jmp wwxxyyzz instruction //if there's no space, inject in place of few instructions if injectsize ...
Read more

json - Hibernate and Jackson (java.lang.IllegalStateException: Cannot call sendError() after the response has been committed) -

json - Hibernate and Jackson (java.lang.IllegalStateException: Cannot call sendError() after the response has been committed) - hello have problem hibernate , jackson. have 2 pojos @entity @table(name = "users") public class user implements serializable { static final long serialversionuid = 4235637833262722256l; @id @generatedvalue private int id; @column(name = "creation_date") private date creationdate; @column(name = "first_name") private string firstname; @column(name = "last_name") private string lastname; @version @column(name = "version") private int version; @column(name = "e_mail") private string email; @column(name = "enabled") private boolean enabled; @column(name = "login") private string login; @column(name = "password") private string password; @jsonmanagedreference("role") @onetomany(mappedby = "user", cascade = cascadetype.all,fetch = fetchtyp...
Read more

C++ 11 "class" keyword -

C++ 11 "class" keyword - i've started using c++ 11 little bit more , have few questions on special uses of class keyword. know it's used declare class, there's 2 instances have seen don't understand: method<class t>(); and class class_name *var; why precede typename keyword class in first example, , keyword pointer in sec example? that known elaborated type specifier , necessary when class name "shadowed" or "hidden" , need explicit. class t { }; // love of god don't t t; t t2; if compiler smart, give these warnings: main.cpp:15:5: error: must utilize 'class' tag refer type 't' in scope t t2; ^ class main.cpp:14:7: note: class 't' hidden non-type declaration of 't' here t t; ^ if class not defined, deed forwards declaration. for example: template <typename t> void method() { using type = typename t::value_type; } method...
Read more