7, 58 56 characters, 22 21 bytes each
00000000011111111222233333444444445555717162234430404053
Try it online!
13131313000000022444444444455557211172000060322351311443
Try it online!
75325101303040432051043451011444112403241040200543216743
Try it online!
Update: Since the first version of this answer, I golfed off a 7 and a 0 – the hello program was slightly rearranged to be able to make use of the 6 rather than needing a 0, and the quine was entirely rewritten to use fewer 7s. The text below has been updated to match; see the edit history for the previous version of this answer.
No cheating with I/O this time: these are all full programs which output to standard output, and (in the case of the second program) input from standard input. The cat program was the hardest of the three to write by far, because it's the only program that requires a loop.
7's character encoding (which is just octal) encodes eight characters per three bytes. This program is thus 21 bytes long (⅜ of 56). Because this is an integer, we don't have to worry too much about the weird sub-byte encoding, but in order to make the programs "conceptually shorter", I ensured that they all ended with a 3 (the interpreter treats trailing 1 bits like trailing whitespace, so the final two bits of the encoding are arguably not part of the program). Note that I can't end a program with a 7 because it would be ignored entirely, causing the program to no longer be 56 characters long (and thus the programs to not be permutations of each other).
Explanations
My usual reminder: 7 has 12 commands, but only 8 of them have names. I use the notation 0, 1, 2, 3, 4, 5 for the commands that append 6, 7, 2, 3, 4, 5 respectively to the top stack element (the last four of these commands cannot appear literally in a program and can only be created at runtime by using them to create a program on the stack).
Quine
00…557171622…53
00…55 An arbitrary string literal
7 Separator between elements of the initial stack
171622…53 Literal representing the main program
The first pass through a 7 program can't do anything more than push literals to the stack (the rightmost goes towards the top of the stack). However, after doing that, the top stack element is implicitly executed (non-destructively; it remains on top of the stack, and a copy is executed). It does the following:
712234436464653
71 Push stack element "7"
2 Duplicate it
23 Use one copy as an I/O routine (sets I/O format 7)
443 Swap the "7" and main program
6 Uneval the main program, and
append it to the stack element below
46 Uneval the second stack element, while
swapping it to the top of the stack
46 Uneval the second stack element, while
swapping it to the top of the stack
5 Execute the new top of stack
(this undoes the uneval and appends it
to the element below)
3 Output (+ some irrelevant side effects)
It's a little hard to follow this, so here's a description of what's happening to the stack. It starts with two stack elements: the arbitrary literal, below the main program (both of these start out in evaluated, ready-to-run, form). The program immediately adds a third (the literal 7), which is (nondestructively) used to set the I/O format (to format 7, "the same format as is used for the source code"). It then works out what source code is most likely to have produced the executable/evaluated main program via using the 6 command (and I intentionally wrote it in a way that would round-trip properly), and appends it to the 7 – this generates a string literal, the source code for the latter half of the quine (from the first 7 onwards). Then it undoes the evaluation of the arbitrary literal below (working out the source code that generated that arbitrary literal, too – source code consisting only of nonbolded characters roundtrips perfectly as they have a very obvious effect on the stack), and prepends that to our calculated second half of the quine's source code, producing the source code of the quine as a whole (and outputs it).
The confusing part is that the 46465 near the end, which undoes the evaluation of the arbitrary literal and prepends it to the rest of the quine's source code, has the two operations (unevaluating and prepending) interleaved with each other. This is because there isn't a direct "append" instruction in 7. Rather, there are two ways to append things – the 6 command does both an unevaluate and an append, and string literals append themselves to the top stack element when executed rather than creating a new stack element. So in order to append two string literals without a net change to the escaping level, the latter needs to be unevaluated in-place (and it needs an empty element beneath to append to due to the other effect of 6), and then executed using 5. The most convenient way to cancel out the side effect of 6 is to use the swap command 4 – this places an empty stack element in between the two elements it's swapping. So we need to interleave swaps in with the unescapes, and this means interleaving the routines that operate on the two relevant stack elements, swapping between the routines every time the stack element swaps.
Incidentally, this is a proper quine under CGCC's definition because the 1 in 716 is used to output the first 7 in the output (in addition to representing itself). (You can observe this by changing this section of code to, e.g., 7101016 – the separator changes to 76767 in the output, and you get a 6767 at the start of the output because the same literal is also output to set the I/O format.)
Cat program
I actually hadn't written a cat program in 7 before, and it's not as trivial a task as it looks.
13131313…72111720000603…43
13131313… Literal representation of program 73737373…
7 Separator between elements of initial stack
2111720000603…43 Literal representation of program 27772000063…43
Two programs, here, which run in (7's usual reverse) sequence.
The program on the left (which runs last) pops the stack (73) four times. It won't have four elements on it at that point, and a pop on an empty stack is defined to exit the program (stack underflow is normally an error, but this is a special case). So the rest of that program never runs, and it gives us a place to put all the digits we have to include (due to the permutation restriction) but aren't using for anything.
The program on the right is more interesting, and implements the cat behaviour. It assumes that a copy of itself will exist on the top of the stack when it starts running (this will always be the case on the first iteration, because 7 leaves the top of stack in place when it starts running it).
The program on the right is also a silly sort of polyglot. The numerical value of a string in 7 is defined as the total number of 1 and 7 characters in it, minus the total number of 0 and 6 characters; other characters are ignored. With six 7s, four 0s and a 6, this string has a numerical value of +1. This is intentional and required for the program to work, because the string in question is used interchangeably as an implementation of the cat program, and a representation of the integer 1, while the program is running. (This sort of polyglotting is pretty unusual, but helped me save the need for a second 6 character, which would have hurt the byte count because the hello program (the longest) doesn't have any natural reason to use one and so we can't just borrow one from its string literal.)
The string literal 20000 is also a polyglot. This is used only as an I/O control string. The numerical value of -4 means "input a character", when we try to interpret it as a character code (input is done by outputting otherwise impossible/illegal values, like negative character codes); the leading 2 means "output character codes as characters". The default character set for character I/O is 8-bit SBCS. So on the first iteration, we configure I/O for byte-at-a-time operation, and reinterpret the same value that does that as -4 and thus input a character in the process. In the subsequent iterations, I/O is already configured as byte-at-a-time, so only the numerical value of -4 matters.
Bearing those factors in mind, we can now look at how the program works:
2777200006322357377443
2 Duplicate top of stack
77200006 Escaped literal 20000 (non-bolded)
7 3 Output literal (actually takes input)
Input is implemented by duplicating the top of stack a number of times equal to the input, off-by-one (so that EOF can be 0, NUL is 1, SOH is 2, etc.). The same off-by-one applies on output. So the stack is now our 1/cat polyglot, below an integer (which is repeated copies of the cat program) representing our input. We can output it immediately to implement cat behaviour.
2777200006322357377443
223 Non-destructive output of top of stack
5 Pop and eval top of stack
73 Pop top of stack
77 Push two empty stack elements
443 Swap those empty elements
After producing our output, we loop by executing ourself again. Or do we?
The program has to halt on EOF. If you look carefully, you'll note that we aren't executing the original cat program (the one with an integer value of 1); that's on the stack just below the element we eval'ed. The stack element actually being executed is the one we just output: the character code that was read in from the user. Remember that this is made up of a number of copies of the cat program, so in most cases we can simply just execute it and it'll work the same way as the original program. However, if the character code we read in is EOF, it'll consist of no copies of the cat program, so there will be nothing to run. We then pop the remaining cat program from the stack, and there are no printing or looping commands left in the program, so it must eventually end up exiting naturally. This gives us a clean exit at EOF, whilst being very very esoteric. (The two 7 commands at the end are clearly pointless, of course; they exist purely to get the numerical value of the cat program right, and don't cost any bytes because they're needed to maintain the permutation property anyway, as they're generated from 1s and we have plenty of those in the hello string literal. The 433 at the end is a no-op, also made from characters that would need to be added somewhere anyway – its purpose is to ensure that the original program ends with a 3.)
Hello program
753…16743
7 Empty padding element on initial stack
53…1 Literal representation of string 53…7
6 Uneval that string (on the first pass!)
7 Separator between elements of the initial stack
43 Modified "print a literal" program
This is a version of the 7 hello-world program, modified a little more extensively than in the original version of this answer.
The standard hello-world program in 7 consists of a string literal followed by 7403 – during the first pass through the program, the literal is evaluated into live executable code, but the 40 swaps it to the top of the stack and unevaluates it (getting back at the original string literal), and the 3 then prints it (and also pops the 463 stack element that's the currently executing code – remember, the top stack element gets executed after the first pass through the program, but is not popped in the process). That's what I did for the first version of this answer.
However, this program needs to contain a 6 somewhere, so that it can be a permutation of the cat program. It's possible to make use of this to save the 0 from the original version of the answer – instead of unevaluating the string literal while the "print a literal" program is executing, we can instead unevaluate it on the first pass through the program (because 6 and 7 commands run immediately). Program execution starts with two empty elements on the stack, so the 6 unevaluates the string literal (returning it to its original form in the source code) and appends it to one of them. That lets us write the program that actually prints the literal as just 43 rather than 463 (so the original source that represents it is just 43 rather than 403).
An unfortunate consequence of this way of doing things (as opposed to the normal way to write a hello-world program) is that the 43 never actually ends up getting popped from the stack. It thus runs again when the end of the program is reached, and ends up crashing the program due to stack exhaustion rather than exiting cleanly. However, we do have the right output on standard output, and that's all that matters.
The literal is, as usual for 7, encoded in a domain-specific language intended for encoding strings; the 5 at the start of the long literal selects this. It contains four different sets of 32 characters (uppercase letters, lowercase letters, digits and common symbols, and rare symbols), with shift codes to switch between them; and within each set, each character is encoded as two octal digits in the 0-5 range (because 6 and 7 are needed as delimiters). Apart from the reinterpretation of 5 bits as two base-6 digits, this encoding wasn't invented for 7; it is in fact the US-TTY encoding (a variant of Baudot), which was commonly used before ASCII was invented, and which is often a little shorter for commonly used strings than ASCII would be, despite containing all the same characters.
Hello, Permutations! requires five shift codes (which can be visualised as HłelloØ, ŁPłermutationsØ!), so it's 20 + 6 = 25 characters long, thus 50 octal digits when encoded as a 7 literal (51 total when allowing for the 5 to select the encoding). This comes to 18¾ bytes, just slightly shorter than the string would be in ASCII.
