生成具有n个不可重复子序列的字符串 [英] Generating string with n non-repeatable subsequences

问题描述

任务是编写一个程序，对于每个给定的自然数n，将生成不太长的文本，这些文本由不太多的符号组成，这些符号具有完全n个不同的子序列。但请记住，0长度的子序列也是子序列。如果文本不同，我们认为子序列是不同的。例如序列ioi有七个子序列（i，o，ii，io，oii，ioi和空子序列）。



我不知道，如何开始咬这个。

有没有人知道如何解决它？



提前感谢



我尝试了什么：



我已经尝试确定子序列数之间的某种关系每一个字母的出现，我也尝试做一个暴力解决方案，但最后，似乎工作的一切都没有任何意义。

解决方案

< blockquote>你必须创建你可能创建的子序列，需要比较，所以你需要一个具有相等功能的SubSequence或Sequence。这个相等的功能可能类似于：

  bool   operator  ==（ const  SubSequence& op）
  bool  isSubsequence（ SubSequence * seq）;  //  如果seq在对象中，则进行一些测试 
  //  其他函数 
 SubSequence（字符串文本）;  //  创建实例 
 SubSequence * allSubsequences（）;  //  函数返回所有子序列的数组 

提示：即使不是所有部分都能正常工作，你也会有希望积分; - ）

这是一项持续竞争的问题（https://sio2.mimuw.edu.pl/c/oi26-1/p/pod/）。请不要在11月13日之前回答这个问题。

The task is to write a program, which for every given natural number n will generate not so long text made of not so big number of signs, which has exactly n different subsequences. But remember that subsequence with 0-length is also the subsequence. We consider subsequences to be different if their text is different. For instance sequence "ioi" has seven subsequences (i,o,ii,io,oii,ioi and empty subsequence).

I have no idea, how to start biting this.
Does anyone have an idea how to solve it?

Thank in advance

What I have tried:

I've already tried to determine some kind of relation between the number of subsequences and a number of appearances of each letter, I also tried to do a brute force solution, but finally, everything, which seemed to work didn't have any sense.

解决方案

You have to create subsequences which you may create, need to compare, so you need a class SubSequence or Sequence which has an "equal" function. This "equal" function may be something like:

bool operator==(const SubSequence &op)
bool isSubsequence(SubSequence *seq);//some test if seq is in object
//other functions
SubSequence(string text);//create instance
SubSequence* allSubsequences();//function which returns an array of all subsequence

Tip: even if not all works some parts will do, and you get hopefully enough points ;-)

This is a problem from an ongoing competition (https://sio2.mimuw.edu.pl/c/oi26-1/p/pod/). Please do not answer this question until November 13.

这篇关于生成具有n个不可重复子序列的字符串的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！