GIDForums  

Go Back   GIDForums > Computer Programming Forums > C++ Forum
User Name
Password
Register FAQ Members List Calendar Search Today's Posts Mark Forums Read

 
 
Thread Tools Search this Thread Rate Thread
  #1  
Old 13-Jun-2004, 05:01
sho sho is offline
Junior Member
 
Join Date: Jun 2004
Posts: 49
sho will become famous soon enough

looking for a way to identify a repetitive sequence of digits in an array or string


Hello, I'm looking for a way to identify a repetitive sequence of digits in an array or string.

The case is that i have an array of 100 integer elements (0-9 in each array position). I have to print out the repeated sequences that are found on it.

For example:

int nums = { 1,5,3,7,2,7,8,2,9,0,3,5,1,2,7,8,2,9,0,3 } // its 20 in length but i will use one of 100 in length

In this case it will print out "278290351" as its the repeating sequence independently of if its repeated complitely (we would supose that if there were more numbers in the array the next 2 would be 5 and 1 to complete the sequence).

Other two different cases would be:

int nums = { 2,5,3,7,6,8,1,2,3,1,1,1,1,1,1,1,1,1,1,1 }

This case the program output would be "1", the repeated sequence.

int nums = { 5,1,3,2,4,2,3,5,1,3,5,1,3,5,1,3,5,1,3,5 }

This case output is "351".


I hope someone could give me any idea. Thx.
  #2  
Old 13-Jun-2004, 09:16
machinated machinated is offline
Regular Member
 
Join Date: Mar 2004
Location: victoria, canada
Posts: 324
machinated has a spectacular aura aboutmachinated has a spectacular aura about
nested for loops. take a look at bubble sort, it should be almost exactly like that except for swapping elements.
__________________
spasms!!!
  #3  
Old 13-Jun-2004, 11:47
tay's Avatar
tay tay is offline
Junior Member
 
Join Date: Jan 2004
Posts: 77
tay will become famous soon enough
int num = {2, 1,2,3, 4, 1,2,3, 5, 1,2,3, 6,6,1, 2, 6,6,1, 6,6, 2};

what is the output for this?
123 is repeated
661 also
66 also repeat
__________________
challenges are make life interesting,
overcome them is make life meaningful.
  #4  
Old 13-Jun-2004, 17:23
sho sho is offline
Junior Member
 
Join Date: Jun 2004
Posts: 49
sho will become famous soon enough
Quote:
Originally Posted by tay
int num = {2, 1,2,3, 4, 1,2,3, 5, 1,2,3, 6,6,1, 2, 6,6,1, 6,6, 2};

what is the output for this?
123 is repeated
661 also
66 also repeat

tay, that would have no output, because its suposed that the sequence to find is going to get repeated after where it was found first searching left to right, without any number in between the repeated sequence.

think of it as the decimals of a division of 2 numbers, once there is a sequence of repeated digits it gets repeated periodically.


machinated, i thought in doing that with nested for loops as you suggest and search for a substing in the array turned into a string, but it gets complicated in that i dunno how long the sequence would be.

it could be a 1-number sequence repeated or it could be more than just one.
  #5  
Old 14-Jun-2004, 12:40
machinated machinated is offline
Regular Member
 
Join Date: Mar 2004
Location: victoria, canada
Posts: 324
machinated has a spectacular aura aboutmachinated has a spectacular aura about
sorry i misunderstood before, I obviously din't read your post carefully.

also output for tay's array would be 6 wouldnt it?
__________________
spasms!!!
  #6  
Old 14-Jun-2004, 13:39
machinated machinated is offline
Regular Member
 
Join Date: Mar 2004
Location: victoria, canada
Posts: 324
machinated has a spectacular aura aboutmachinated has a spectacular aura about
sho i've done a little rough draft, and i ran my code a couple of times and it seems to work. i'm posting the code as it is right now but keep in mind that it is a rough draft and might have several bugs or might not work properly in all the situations. Just use the code as a reference or a starting point.
CPP / C++ / C Code:

int main()
{
  int array[10];    //array size 10
  int dist = 0;     //distance between corresponding elements of the sequences
  int x2,dist2;
  bool sequence;  //if sequence exists or not
    
  for(int x=0;x<10;x++)  //get the values for the array
  {
    cout<<"enter value for "<<x<<endl;
    cin>>array[x];
  }
    
  for(int x=0;x<10;x++)   //outer loop
  {
    for(int y=x+1;y<10;y++)   //inner loop
    {
      if(array[x]==array[y])   //if a  match is found between two elements
      {
        sequence=true;   //assume sequence to be true
        x2=x;       //retain value of x
        dist=y-x;  //distance is the number of elements between the corresponding sequence elements
        dist2=dist;//retain dist value
        for(;dist>0;dist--) //run the inner loop as many times as the value of y-x
        {
          if(array[x2]!=array[x2+dist2]) //if at any time the corresponding elements don't match between the sequences,
            sequence=false;//the sequences doesn't exist
          x2++;
        }
            
        if(sequence) //if there was  a sequence,
        {
          for(int a=x;a<y;a++) //print it
            cout<<array[a]<<" ";
          cout<<endl;
        }
      }
    }
  }
  system("pause");
  return 0;

how the code works: basically we're incrementing thru the array comparing each element with the rest of the array. if an element matches with any of the following elements in the array, we assume that they are a repeating sequence. Now to compare the elements following the original element with the elements following the identical or match element. If at any point the sequences don't match, there is no sequence repetition at all.
Note that this is just a basic mechanism and you will have to tailor it to meet your additional criteria such as if there seems to be a repetitive sequence and the array ends, there is an assumption that the sequence would have been valid if there would have been additional space in the array.
__________________
spasms!!!
  #7  
Old 14-Jun-2004, 13:45
eXiLe eXiLe is offline
New Member
 
Join Date: Jun 2004
Posts: 10
eXiLe is on a distinguished road
it seems to be working, but i didn't compile. i just think it'll be working in most cases. i'm not sure but i think something's missing. i don't have any time right now to compile and test it, but i'll advise you to review it and test it in lots of different situations (arrays)
  #8  
Old 14-Jun-2004, 13:51
machinated machinated is offline
Regular Member
 
Join Date: Mar 2004
Location: victoria, canada
Posts: 324
machinated has a spectacular aura aboutmachinated has a spectacular aura about
yes that would be upto sho to do any additional work. I've provided him with a starting point.
__________________
spasms!!!
  #9  
Old 15-Jun-2004, 00:59
sho sho is offline
Junior Member
 
Join Date: Jun 2004
Posts: 49
sho will become famous soon enough
Thumbs up

Thank you machinated, now i could finish the program i had begun with help of your sample code.

It helped me out to figure another way to implement it and add the validation to meet my criteria.
 
 

Recent GIDBlogStupid Management Policies by crystalattice

Thread Tools Search this Thread
Search this Thread:

Advanced Search
Rate This Thread
Rate This Thread:

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

vB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Forum Jump

Similar Threads
Thread Thread Starter Forum Replies Last Post
Read a .html file, check that file for links salemite C Programming Language 10 17-Jan-2008 08:56

Network Sites: GIDNetwork · GIDWebHosts · GIDSearch · Learning Journal by J de Silva, The

All times are GMT -6. The time now is 03:00.


vBulletin, Copyright © 2000 - 2008, Jelsoft Enterprises Ltd.