Remapping ASCII

CJam, 356 186 168 131 126 111 99 96 94

"_|`'~,Y/G>z`|"_~

Try it online in the CJam interpreter.

Output

"_|`'~,Y/G>z[ \$&(*.02468:<@BDFHJLNPRTVXZ^bdfhjlnprtvx!#%)+-13579;=?ACEIKMOQSUW]acegikmoqsuwy{}

Idea

Using a variation of a technique common in CJam quines, we sort the printable ASCII characters by whether they appear in the source code, and the non-appearing ones – with two exceptions – by their code points' parity bits.

With the proper source layout, we also manage to sort the source code characters – with one exception – by their frequencies.

Special care has to be taken that two adjacent characters do not appear one after the other for the first time in the source code, as this would invalidate the answer.

Code

"             "_~  Push a string, duplicate it and evaluate the copy.
 _|                Perform the set union of the original string with itself.
                   This is just an "excuse" to introduce the underscore.
   `               Inspect the string (surrounds it with double quotes).
    '~,            Push the string of Unicode characters before the tilde.
       Y/          Divide it into pairs.
         G>        Discard the first 16 pairs (control characters).
           z       Zip. This interleaves the pairs, ordering the characters
                   by their code points' parities.
            `      Inspect the array, i.e., push its string representation.
             |     Perform set union with the string of source code characters.

Brainfuck, 1692 826 765

(Still) Unoptimized, I know. I'm working on it (leave opts in the comments).

++[------>+<]>.++.---[-->+++<]>-.[->+++++++++<]>.--[----->+<]>.[-->+++<]>+.++.>+++[<---------->-]<-[-->+<]>-++.>++[>+++<-]>[<<++.>>-]<<++++.++.++.++.++.++.++++>>++++[<++++++++>-]<[<++.>-]<---.++.-->+++[>+++++<-]>-[<<--.>>-]<<---->++++[>+++++<-]>++[<<--.>>-]<<------.--.--.--.--.

Output:

+->.<[] "$&(*,02468:@BDFHJLNPRTVXZ\^`bdfhjlnprtvxz|~{}ywusqomkigeca_YWUSQOMKIGECA?=;97531/)'%#!

I'm already utilizing overflow on 8bit cells to some extent, but I guess you could still optimize it. Though that would decrease the use of cheap chars :).

Pyth, 173 170

Code

-so%CN2rd\~p"p~\dr2NC%os-

Output

p~\dr2NC%os- "$&(*,.0468:<>@BDFHJLPRTVXZ^`bfhjlntvxz|!#')+/13579;=?AEGIKMOQSUWY[]_acegikmquwy{}

Hardcoding a quine-like string. Conveniently, the " character is very near the start of the generated string. Prints even then odd characters after the "quine".

Much thanks to Dennis for saving 3 points, and making the code a palindome!

Try it here