Solved

queue permutations

Posted on 2001-06-19
21
451 Views
Last Modified: 2012-05-04
we are offered two queues, 'q0' and 'q1'. a collection of numbers are input into these queues. the number one is given first followed by two etc(1,2,3,..n). input sequences can be permuted in different orders by executing the queue operations q0.enq, q1.enq, q0.deq, q1.deq, in a particular order. for example, the input sequence 1,2,3, can yield five different outputs:

output    control sequence
1,2,3     q0.enq,q1.enq,q0.enq,q0.deq,q1.deq,q0.deq
1,3,2     q0.enq,q0.enq,q1.enq,q0.deq,q1.deq,q0.deq
2,1,3     q0.enq,q1.enq,q1.enq,q1.deq,q0.deq,q1.deq
2,3,1     q0.enq,q1.enq,q1.enq,q1.deq,q1.deq,q0.deq
3,1,2     q0.enq,q0.enq,q1.enq,q1.deq,q0.deq,q0.deq
3,2,1     not possible

not all permutations on n integers are possible as output, as 3,2,1 shows.  how would i write an algorithm that determines if the desired output sequence is possible,and if so, which sequences leads up to it. To do this, we will attach two control numbers to the sequence, one number for the enqueues and one for the dequeues. Interpret an 'qo.enq' as a '0' and 'q1.enq' as a '1', so that the sequence of enqueues becomes a string of 0's and 1's, that can be interpreted as a binary number. for example

output  enq-number    deq-number
1,2,3   (010)=2       (010)=2
1,3,2   (001)=1       (101)=5
2,1,3   (011)=3       (101)=5
2,3,1   (011)=3       (110)=6
3,1,2   (001)=1       (100)=4
3,2,1   not possible
0
Comment
Question by:marvin
  • 10
  • 4
  • 3
  • +3
21 Comments
 
LVL 3

Expert Comment

by:MDarling
ID: 6207687
We aren't allowed to do homework for you.  It is grounds for dismisal for you to ask, and for us to do it.

If you post some code and ask for help with problems, that would be fine.

Regards,
Mike.
0
 
LVL 2

Expert Comment

by:Andrey_Kulik
ID: 6209850
I know algorith
but

1,2,3   (000)=0       (000)=0

I is possible ??

Andrey

0
 
LVL 2

Expert Comment

by:Andrey_Kulik
ID: 6210667
Hi

sample input : "012" or "0231" or "2563014"

#include <vector>
#include <iostream>
#include <ostream>
#include <string>
#include <algorithm>
#include <functional>

using namespace std;

void main(void)
{
     string s;
     cout << "Input number : ";
     cin >> s;
         
     int count = s.length();
     vector<int> map(count), prm(count); // prm - permutation

     // convert string representation to int
     for (int i = 0; i < count; i++)
          map[s[i] - '0'] = prm[i] = i;

     do
     {
          copy(prm.begin(), prm.end(), ostream_iterator<int>(cout, ","));
          cout << " ";

          string deq(count, '0'), enq(count, '0');

          int deqInt = 0, enqInt = 0, q1pos = 0, q2pos = 0;

          vector<bool> f(count, false);

          for (int j = 0; j < count; j++)
          {
               int pos = map[prm[j]];

               bool q1Posibility = find(f.begin() + q1pos, f.begin() + pos, false) != f.begin() + pos;
               bool q2Posibility = find(f.begin() + q2pos, f.begin() + pos, false) != f.begin() + pos;

               if (q1Posibility && q2Posibility && q2pos != 0)
               {
                    cout << "not possible" << endl;
                    break;
               } else
               if (q1Posibility)
               {
                    deq[j] = '1';
                    enq[pos] = '1';
                    deqInt |= 1 << j;
                    enqInt |= 1 << pos;
                    q2pos = pos + 1;
               } else
                    q1pos = pos + 1;
               f[pos] = true;
          }

          if (j >= count)
               cout << "(" << enq << ") = " << enqInt << "   ("<< deq << ") = " << deqInt << endl;

     } while (next_permutation(prm.begin(), prm.end()));
}


Andrey
0
 
LVL 30

Expert Comment

by:Axter
ID: 6210705
Andrey_Kulik,
It's agaisnt EE polciy to post homework answers.
0
 
LVL 2

Expert Comment

by:Andrey_Kulik
ID: 6210763
This question is an ALGORITHM!

EE hasnot topic about algorithms...

it's really bad... computing is not only coding

Andrey
0
 
LVL 1

Expert Comment

by:Moondancer
ID: 6210765
It is against policy to answer homework questions here at EE. I am removing the points from this question.

Moondancer
Community Support Moderator @ Experts Exchange
0
 
LVL 2

Expert Comment

by:Andrey_Kulik
ID: 6210790
i do my points in different topics because i'm algo-spec.

Home work --- sorting an array

but this algorithm is not trivial

Andrey
0
 
LVL 1

Expert Comment

by:Moondancer
ID: 6210795
Points have been refunded.

I will now reject the proposed answer, and will delete the question late in the day so partcipants can see the information provided here.  Rather than answering what appears to be a homework question, PLEASE!:

-advise them that it is against policy
-tell them why you won't help and then stay out of it, or offer them only guidance and/or direction
-immediately post a Q at community support to report it so moderators can appropriately handle it.

Moondancer
Community Support Moderator @ Experts Exchange

0
 
LVL 2

Expert Comment

by:Andrey_Kulik
ID: 6210807
IOAAE ou MOONDANCER

I? iiieia??u ?oi ia?ia ae?i?eoi ?i?a?eaa?o. I?e??i ooo aiia?iyy ?aaioa? ou ?ai au ???i ??i ?a?eae.

A?? ia oai?e ?ia??oe...

A???e?u ao?ee

Warwar
0
 
LVL 2

Expert Comment

by:Andrey_Kulik
ID: 6210815
Povtory special'no latinicej

MUDAK ty MOONDANCER

Kakya k chertu domashnyaya rabota. Narod algoritm ne znaet. Ty by ego hren zdelal!!!
Vse na tvoej sovesti
Derzhis' durik

Warwar
0
How to run any project with ease

Manage projects of all sizes how you want. Great for personal to-do lists, project milestones, team priorities and launch plans.
- Combine task lists, docs, spreadsheets, and chat in one
- View and edit from mobile/offline
- Cut down on emails

 
LVL 30

Expert Comment

by:Axter
ID: 6210849
Andrey_Kulik,
>>Home work --- sorting an array

Sorry Andrey_Kulik, but it doesn't matter how difficult or non-trivial the assignment.  You can not do the homework.
If you want to help the questioner get to the answer, that's find, but you can not provide the answer.
You can assist.
0
 
LVL 2

Expert Comment

by:Andrey_Kulik
ID: 6210916
WHY HOME WORK

IT'S ALGORIHTM

If you think that it's home work -- DO IT NOW

what do you know about algorithm's ?? Your programming experience == 0 if you don't know algorithm for a problem

warwar



0
 
LVL 30

Expert Comment

by:Axter
ID: 6210967
Andrey_Kulik,
>>If you think that it's home work -- DO IT NOW

I can not do it because it is homework.
I don't think you'r understanding me, so I'll let the moderator talk you through this.
0
 
LVL 2

Expert Comment

by:Andrey_Kulik
ID: 6210983
ok
see you...
0
 
LVL 2

Expert Comment

by:Andrey_Kulik
ID: 6211011
Can you determine is this home work or not ?
Why you ?... You ignore my opinion :-/  is this really ok?

almost all question on EE -- home work or stupid questions.
I do ONLY algorithm questions because it's more hard then others

warwar
0
 
LVL 1

Expert Comment

by:Moondancer
ID: 6211076
I will update this question as soon as additional information is received from a C++ Programming specific Moderator, this has been escalated.

I do not understand the posting you made in another language, sorry.

Moondancer
Community Support Moderator @ Experts Exchange
0
 
LVL 1

Expert Comment

by:Moondancer
ID: 6211375
Thanks for the additional information, Andrey.  Please don't feel that you are being ignored, I've spent
a great deal of time working to get additional Topic-specific expert and Moderator to add insight on
this.  With the thousands of questions to be handled, I'm doing this as quickly as I can.  I will update
you as soon as I have a definitive response.  I responded to this already earlier today and the comment
does not appear hear, so I'll add this again.

There are no "stupid" questions, since clearly people have a question and pay points to get help.  The
line is drawn, though, when answers are given to homework questions, although guidance is OK.   This
is all in the Member Agreement accepted by all who participate here, and the goal is to maintain "academic
honesty".  Here is the link to the Agreement.

http://www.experts-exchange.com/jsp/infoMemberAgreement.jsp

Thanks for you patience, I will respond as quickly as I receive what is needed to further clarify the
specific issue here.

Moondancer
Community Support Moderator @ Experts Exchange
0
 
LVL 2

Expert Comment

by:Andrey_Kulik
ID: 6211430
XML and Java topic has some questions about algorithm of comparing two XML with the same DTD... Is this home work or not?
Almost all program products have set of algorithms in the source. if I write "Mathematica 5.0" and don't know some  algorithm can i ask it ??

I also pay my points for this.

Andrey
0
 
LVL 7

Accepted Solution

by:
linda101698 earned 0 total points
ID: 6240683
marvin,
Could you help us resolve this issue?  Please explain what you are using this algorithm for.

Some of the experts feel that it is a homework project.    The general policy decided on by the community follows:

HOMEWORK
There has been several discussions among the experts about doing homework assignments.  The general conclusion among the experts is to give guidance but not to actually do the homework for the person.  

The purpose of homework is for you to learn and if an expert does it for you, you are not learning how to do it for yourself.  Please keep this in mind when asking questions at the site.  You are not really helping the student if you do their assignment for them.  It's better to give guidance and help along the way but an important part of learning is actually doing the work yourself.


The experts are happy to help if you have problems but do not want to do the entire assignment for you.

We need your input to close this question.

Linda Gardner
Customer Service @ Experts Exchange
0
 

Author Comment

by:marvin
ID: 6241303
i am not wanting my homework done for me. I apologize and will not ask such a question again. I resolved the problem on my own. I understand your comment and agree.
0
 
LVL 7

Expert Comment

by:linda101698
ID: 6265003
Thanks for responding marvin.

Is it okay with everyone if I delete this question and refund marvin's points?

Linda
0

Featured Post

Find Ransomware Secrets With All-Source Analysis

Ransomware has become a major concern for organizations; its prevalence has grown due to past successes achieved by threat actors. While each ransomware variant is different, we’ve seen some common tactics and trends used among the authors of the malware.

Join & Write a Comment

Often, when implementing a feature, you won't know how certain events should be handled at the point where they occur and you'd rather defer to the user of your function or class. For example, a XML parser will extract a tag from the source code, wh…
IntroductionThis article is the second in a three part article series on the Visual Studio 2008 Debugger.  It provides tips in setting and using breakpoints. If not familiar with this debugger, you can find a basic introduction in the EE article loc…
The viewer will learn how to pass data into a function in C++. This is one step further in using functions. Instead of only printing text onto the console, the function will be able to perform calculations with argumentents given by the user.
The viewer will learn how to user default arguments when defining functions. This method of defining functions will be contrasted with the non-default-argument of defining functions.

762 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

18 Experts available now in Live!

Get 1:1 Help Now