queue permutations

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
marvinAsked:
Who is Participating?

Improve company productivity with a Business Account.Sign Up

x
 
linda101698Connect With a Mentor Commented:
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
 
MDarlingCommented:
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
 
Andrey_KulikCommented:
I know algorith
but

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

I is possible ??

Andrey

0
Get your problem seen by more experts

Be seen. Boost your question’s priority for more expert views and faster solutions

 
Andrey_KulikCommented:
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
 
AxterCommented:
Andrey_Kulik,
It's agaisnt EE polciy to post homework answers.
0
 
Andrey_KulikCommented:
This question is an ALGORITHM!

EE hasnot topic about algorithms...

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

Andrey
0
 
MoondancerCommented:
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
 
Andrey_KulikCommented:
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
 
MoondancerCommented:
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
 
Andrey_KulikCommented:
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
 
Andrey_KulikCommented:
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
 
AxterCommented:
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
 
Andrey_KulikCommented:
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
 
AxterCommented:
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
 
Andrey_KulikCommented:
ok
see you...
0
 
Andrey_KulikCommented:
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
 
MoondancerCommented:
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
 
MoondancerCommented:
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
 
Andrey_KulikCommented:
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
 
marvinAuthor Commented:
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
 
linda101698Commented:
Thanks for responding marvin.

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

Linda
0
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

All Courses

From novice to tech pro — start learning today.